|
|
עמוד:160
מסלול פשוט - ( simple path ) מ 0 לול שאין בו אף מעגל . שאלת 4 . 5 האם ההגדרה הבאה שקולה להגדרה של מסלול פשוט ? נמקו את תשובתכם . מסלול פשוט הוא מסלול שבו אף קדקוד של הגרף לא מופיע יותר מפעם אחת . באיור 4 . 10 לעיל ישנם מסלולים שונים מהקדקוד A לקדקוד . B מסלול A ^ B : 1 A ^ C ^ D ^ B : 2 ^^^^^ B ^ C מסלול A ^ - - ^ D - ^ B : 3 מסלול A ^ B- > C ^ D ^ B ^ C ^ D ^ B 4 שלושת המסלולים הראשונים נקראים מסלולים פשוטים , אך מסלול 4 אינו מסלול פשוט . קל לראות כי אם קיים מסלול ( כגון מסלול ( 4 בין שני קדקודים בגרף , אז קיים ביניהם גם מסלול פשוט . באופן אנלוגי ניתן להגדיר כך גם מעגל פשוט ( אף קדקוד אינו מופיע יותר מפעם אחת , חוץ מהקדקוד הראשון . ( הערה : מעתה נעסוק במסלולים ( מעגלים ) פשוטים , אלא אם יצוין במפורש אחרת . שאלה 4 . 6 נתון הגרף הזה :
|
|