עמוד:218

^ הגדרה פורמלית של בעיית המסלול הקצר 5 . 3 . 1 גרף קשיר לפני שנתאר באופן פורמלי את הבעיה עלינו להגדיר מהו גרף קשיר : רכיב קשיר - ( connected complete ) קבוצה מקסימלית של קדקודים בגרף לא מכוון שבה יש מ 0 לול פשוט בין כל שני קדקודים בגרף . קדקוד בודד ללא שכנים ייקרא גם כן רכיב קשיר . דוגמה 5 . 5 להלן גרף י בגרף ישנו רכיב קשיר אחד { a , b , c , d , e ] מאחר שמכל קדקוד קיים מסלול לכל קדקוד אחר . לעומת זאת , בדוגמה 5 . 6 מוצג גרף שבו ישנם שלושה רכיבים קשירים . 5 . 2 . 4 גרסה - 4 המסלול הקצו בין זוג קדקודים נתון בגרסה זו המטרה למצוא את המסלול הקצר ביותר בין זוג קדקודים גינונים בגרף . גרסה זו היא מקרה פרטי של גרסה . 3 אייר 5 . 5 גרף עם רכיב קשיר אחד

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר