|
|
עמוד:203
ג . כתבו אלגוריתם המקבל כקלט את הגרף , G והבודק אם G מכיל "תת-גרף מלא" מגודל . 3 ניתן להשתמש באלגוריתם שכתבתם בסעיף . 'ב שאלה 4 . 32 נייצג מסלול בגרף על-ידי רשימה L המייצגת את צלעות המסלול לפי סדר . לדוגמה , לגבי הגרף שלהלן : נייצג את המסלול / ( A , B ) , ( B , D ) , ( D , )) המתחיל בקדקוד , A עובר דרך , 5 אחריו דרך D ואחריו דרך C על-ידי הרשימה . L = ( A , B , C , D ) הרשימה L מכילה ארבעה קדקודים , C , B , A ם , ומייצגת שלוש צלעות ( לפי סדר המסלול . ( נתון אלגוריתם האמור למצוא מסלול מעגלי בעל המשקל המינימלי , העובר בדיוק פעם אחת בכל קדקוד בגרף שלם ( זהו גרף שבו כל הקדקודים מחוברים זה לזה . ( נסמן c- את סדרת הקדקודים המייצגת את המסלול שנבנה . נסמן ב-ט את הקדקוד האחרון במסלול שנבנה . תחילה L היא סדרה ( רשימה ) ריקה . . 1 בחר קדקוד כלשהו , שבו מתחיל המעגל , והצב אותו ב ^ . 2 הצב את W ; [/ -ב . 3 כל עוד L אינה מכילה את כל הקדקודים שבגרף , בצע י 3 . 1 בחר צלע ( U , V ) בעלת משקל מינימלי מבין כל הצלעות היוצאות £ / -מ כך V-v אינה ב ;^ 3 . 2 הוסף את הקדקוד V שבחרת -, L-b 3 . 3 הצב את . £ / -ב ^ . 4 סייס לולאה . . 5 הוסף £ -ל את הקדקוד . W . 6 סיים .
|
|