|
|
עמוד:204
א . לפניכם הגרף השלם הזה הפעילו את האלגוריתם על הגרף השלם הנתון , ורשמו את המסלול המעגלי שמתקבל ( התחילו את הסריקה מהקדקוד . ( A ב . . 1 האם מן האלגוריתם תמיד מתקבל מעגל העובר פעם אחת בכל קדקוד ? נמקו את תשובתכם . . 11 האם מן האלגוריתם תמיד מתקבל מעגל בעל משקל מינימלי ? נמקו את תשובתכם . שאלה 4 . 33 נתון גרף G = ( V , E ) כאשר קבוצת הקדקודיס £ -ו קבוצת הצלעות . קבוצת הקדקודים ( V £ V ) , V נקראת "קדקודי , "כיסוי אס כל צלע בגרף " מחוברת" מצד אחד לפחות לקדקוד . 1 '" -שב כלומר , אם ( a , b ) צלע , £ -ב אז a או b שייכים ל-י / ו . ( קבוצת הקדקודים '' V מכסה '' את כל צלעות הגרף . ( דוגמה :
|
|