תוכנית פסגה · גרפים מכוונים ובעיית המנעול
תרגיל 2: חוקרים: מתי אפשר לעבור בכל הקשתות?
נסו לעבור בכל קשת בדיוק פעם אחת, לפי החצים. מותר לבחור את נקודת ההתחלה ולבקר בצומת יותר מפעם אחת.
מיינו את הגרפים לשלוש קבוצות - יש מעגל אוילר; יש מסלול פתוח בלבד; אין מסלול אוילר. כתבו מסלול שמוכיח שאפשר, או נימוק שמסביר למה אי אפשר.
מה משותף לגרפים בכל קבוצה?
- בדקו כניסות ויציאות. נסחו תנאי לצומת במסלול סגור.
- מה משתנה בצומת ההתחלה ובצומת הסיום של מסלול פתוח? מה קורה בכל שאר הצמתים?
- בגרפים ג ו־ד אותם חיבורים, ורק כיוון של קשת אחת שונה. מדוע זה חשוב?
- הסבירו את התנאים שהצעתם בעזרת הכניסות והיציאות לאורך מסלול. אל תסתפקו במספר הניסיונות שנכשלו.
- האם אפשר להפוך את סדר הצמתים של מסלול חוקי ולקבל תמיד מסלול חוקי נוסף?
לחצו על צומת התחלה. צהוב - המיקום שלכם; כחול מקווקו - קשת שכבר נוצלה. אפשר לבטל צעדים ולנסות שוב.