|
|
עמוד:205
קבוצת הקדקודים { 2 , 3 } היא קדקודי כיסוי , כיוון שהצלעות ( 4 , 3 ) , ( 2 , 3 ) , ( 3 , 1 ) מחוברות לקדקוד , 3 הצלע ( 1 , 2 ) מחוברת לקדקוד , 2 ואין יותר צלעות בגרף . נתון האלגוריתם שלהלן למציאת קדקודי כיסוי v לגרף נתון ? . G- ( V , E ) . 1 אפס את . V . 2 העתק את ס ;/? -ל . 3 אם R אינו מכיל צלעות , סיים . . 4 מצא את הקדקוד בעל הדרגה הגבוהה ביותר שנמצא , /? -ב והוסף אותו Ac ( אם יש יותר מקדקוד אחד כזה , בחר אחד כרצונך ( . . 5 מחק R-r 2 את הקדקוד שמצאת , 4-ב ואת כל הצלעות המחוברות אליו ; . 6 חזור . 3-ל א . הפעילו את האלגוריתם על כל אחד מהגרפים שלהלן , ורשמו מהם קדקדי הכיסוי שהתקבלו . רשמו את התוכן של V בכל שלב . גרף : 1 גרף : 2
|
|