תוכנית פסגה · גרפים מכוונים ובעיית המנעול
תרגיל 5: מהמנעול לגרף מכוון
איך אפשר לייצג את בעיית המנעול בגרף מכוון כך שהמשימה תהיה לעבור בכל קשת בדיוק פעם אחת?
- מה ייצג צומת? מה תייצג קשת? הסבירו את הבחירה שלכם.
- איך תייצגו את הקודים 14, 41 ו־11? האם 12 צריך להיות קשת בגרף?
- ציירו את הגרף ובדקו את דרגות הכניסה והיציאה. באיזה צומת חייב מסלול אוילר להתחיל, ובאיזה צומת עליו להסתיים? נמקו.
- 35
- 71
- 22
- 64
- 58
- 17
- 33
- 46
- 82
- 11
- 53
- 77
- 28
- 61
- 44
- 85
- 14
- 32
- 67
- 55
- 41
- 88
- 76
- 23
- 47
- 52
- 16
- 83
- 66
- 25
- 74
- 38
- 72
אחרי שהצעתם ייצוג - פתחו את הגרף לבדיקה
צומת מייצג את הספרה האחרונה. קשת מכוונת מ־a ל־b מייצגת את הקוד התקף ab. קוד שאינו ברשימה אינו קשת בגרף.
בחרו צומת התחלה ואז לחצו על הצמתים הבאים. לחיצה נוספת על אותו צומת משתמשת בלולאה, אם עדיין לא נוצלה. במסך צר אפשר לגלול את הגרף הצדה.
רצף הלחיצות המתאים למסלול שלכם:
-
אורך רצף הלחיצות: 0
מצאו מסלול אוילר וקראו את רצף הלחיצות המתקבל. השוו את אורכו לחסם שמצאתם.
סכמו את ההוכחה בשני חלקים: מדוע אי אפשר בפחות לחיצות, ומדוע הרצף שמצאתם מספיק.