סיכום התרגילים, שאלות ההרחבה והפתרונות
בכל התרגילים הקשתות דו־סטריות. מסלול אוילר עובר בכל קשת בדיוק פעם אחת; מותר לבקר באותו צומת יותר מפעם אחת. מסלול סגור, שמתחיל ומסתיים באותו צומת, נקרא כאן גם מעגל אוילר.
במפה 16 צמתים ו־28 רחובות. מותר לבחור את נקודת ההתחלה.
היעד: לעבור בכל רחוב בדיוק פעם אחת ולחזור לנקודת ההתחלה.
קיים מעגל אוילר: הגרף מחובר, וכל הדרגות זוגיות. דוגמה למעגל מתאים:
1 → 2 → 3 → 4 → 8 → 7 → 3 → 8 → 12 → 16 → 15 → 11 → 10 → 6 → 5 → 9 → 10 → 14 → 13 → 9 → 14 → 15 → 12 → 11 → 7 → 6 → 2 → 5 → 1
כל ניקיון מלא חייב לעבור בכל רחוב לפחות פעם אחת. המסלול הזה עובר בכל אחד מהם בדיוק פעם אחת, ולכן אורכו הקטן ביותר האפשרי. אפשר להתחיל בכל צומת בגרף.
במפה 16 צמתים ו־27 רחובות.
היעד: לעבור בכל רחוב בדיוק פעם אחת. מותר להתחיל ולסיים בצמתים שונים.
לצמתים 6 ו־7 דרגה 3, ולכל שאר הצמתים דרגה זוגית. לכן יש מסלול אוילר פתוח בלבד: מתחילים באחד משני הצמתים האי־זוגיים ומסיימים בשני. לדוגמה:
6 → 2 → 5 → 1 → 2 → 3 → 4 → 8 → 7 → 3 → 8 → 12 → 16 → 15 → 11 → 10 → 6 → 5 → 9 → 10 → 14 → 13 → 9 → 14 → 15 → 12 → 11 → 7
אפשר גם לעבור באותו מסלול בכיוון ההפוך. אי אפשר להתחיל בצומת אחר, ואי אפשר לחזור להתחלה בלי לחזור על קשת.
במפה 16 צמתים ו־26 רחובות. אפשר לבחור היכן להתחיל והיכן לסיים.
היעד: לבדוק אם אפשר לעבור בכל רחוב בדיוק פעם אחת, ולנמק את המסקנה.
אי אפשר. לצמתים 6, 7, 10 ו־11 דרגה 3, ולכן יש ארבעה צמתים אי־זוגיים.
בצומת שאינו ההתחלה או הסיום, כל כניסה צריכה להשתדך ליציאה בקשת אחרת. במסלול אחד יש רק שתי נקודות שיכולות להיות חריגות: ההתחלה והסיום. ארבעה צמתים אי־זוגיים אינם יכולים להתאים. זו הוכחת אי־אפשרות, שאינה תלויה במספר הניסיונות שנכשלו.
שישה גרפים מחוברים חולקו לשלוש קבוצות: בגרפים א ו־ב יש מעגל אוילר; בגרפים ג ו־ד יש מסלול פתוח בלבד; בגרפים ה ו־ו אין מסלול אוילר.
השאלה: איזו תכונה מבדילה בין הקבוצות, ולמה?
א ו־ב: אין צמתים אי־זוגיים. בגרף א כל הדרגות הן 2; בגרף ב לצומת 3 דרגה 4 ולשאר הצמתים דרגה 2. לכן קיים מעגל.
ג ו־ד: בדיוק שני צמתים אי־זוגיים. בגרף ג אלה 1 ו־5, שדרגתם 1; בגרף ד אלה 1 ו־3, שדרגתם 3. הם יהיו ההתחלה והסיום.
ה ו־ו: ארבעה צמתים אי־זוגיים. בגרף ה לצומת 1 דרגה 3 ולשלושת האחרים דרגה 1; בגרף ו כל הדרגות הן 3. לכן אין מסלול.
התכונה החשובה היא מספר הצמתים בעלי דרגה אי־זוגית. צורת הציור והערך המדויק של הדרגה אינם קובעים לבדם את התשובה.
בגרף מחובר שכל דרגותיו זוגיות הדגמנו כיצד בונים מעגל אוילר.
שאלת ההרחבה: מסירים את הקשת בין 1 ל־2. איך אפשר להיעזר בשיטה למציאת מעגל כדי למצוא מסלול פתוח?
בהדגמה התחלנו במעגל 1 → 2 → 3 → 4 → 1 ושילבנו בו שלושה סיבובים: 2 → 5 → 6 → 2, 3 → 9 → 10 → 3 ו־4 → 7 → 8 → 4. התקבל:
1 → 2 → 5 → 6 → 2 → 3 → 9 → 10 → 3 → 4 → 7 → 8 → 4 → 1
מדוע זה עובד? בצומת שאינו ההתחלה, כל כניסה משאירה אפשרות ליציאה. לאחר הוצאת קשתות של מעגל, מספר הקשתות שנותרו בכל צומת עדיין זוגי. אם נותרו קשתות, החיבור של הגרף מבטיח שקיים צומת במעגל שכבר בנינו שממנו אפשר להמשיך. בכל סיבוב משתמשים בקשתות חדשות, ולכן התהליך מסתיים.
פתרון שאלת ההרחבה: מחזירים זמנית את הקשת 1–2 ומוצאים מעגל אוילר. אחר כך מסירים אותה וחותכים בה את המעגל: מתחילים מיד אחרי הקשת שהוסרה וממשיכים עד לקצה השני שלה. בדוגמה שלנו מתקבל:
2 → 5 → 6 → 2 → 3 → 9 → 10 → 3 → 4 → 7 → 8 → 4 → 1
כל הקשתות שנותרו מופיעות בדיוק פעם אחת. ההתחלה והסיום הם 2 ו־1, שהפכו לצמתים האי־זוגיים בעקבות ההסרה.
השאלון כולל תשע שאלות: חמש שאלות חזרה וארבע שאלות חשיבה והרחבה. הפתרונות שלהלן כוללים גם את הנימוקים.
פתיחת השאלוןמהי הדרגה של צומת 3 בגרף?
4
הדרגה היא 4: לצומת 3 מחוברות הקשתות אל 1, 2, 4 ו־5.
איזה מסלול אוילר קיים בגרף?
מסלול פתוח בלבד — בין 1 ל־3
הגרף מחובר. לצמתים 1 ו־3 דרגה 3 ולשניים האחרים דרגה 2. לכן יש מסלול פתוח בלבד, מ־1 ל־3 או להפך.
מדוע אין בגרף הזה מסלול אוילר?
מפני שיש ארבעה צמתים אי־זוגיים
כל ארבעת הצמתים הם בדרגה 3. במסלול אחד יכולים להיות לכל היותר שני צמתים אי־זוגיים: ההתחלה והסיום.
בנינו את המעגל הכחול, ואז את המעגל הכתום. איזה רצף משלב אותם למעגל אוילר?
המעגל הכחול: 1 → 2 → 3 → 1. המעגל הכתום: 3 → 4 → 5 → 3.
1 → 2 → 3 → 4 → 5 → 3 → 1
כשמגיעים ל־3 במעגל הכחול, יוצאים לסיבוב 3–4–5–3, ואז ממשיכים מ־3 ל־1. כך כל שש הקשתות מופיעות בדיוק פעם אחת.
מדוע לא ניתקע בצומת שאינו נקודת ההתחלה?
מתחילים בגרף שכל דרגותיו זוגיות ומתקדמים בקשתות שטרם עברנו בהן, עד החזרה הראשונה להתחלה. הסבירו במשפט או שניים בעזרת כניסה ויציאה.
בכל ביקור קודם בצומת שאינו ההתחלה השתמשנו בזוג קשתות: כניסה ויציאה. הדרגה המקורית זוגית, ולכן אחרי הכניסה החדשה נשאר מספר אי־זוגי של קשתות שלא נוצלו — לפחות קשת אחת שאפשר לצאת בה.
נועה טוענת: ״כל הדרגות זוגיות, אז יש מעגל אוילר אחד שעובר בכל הקשתות״. האם היא צודקת בגרף הזה?
הסבירו בקצרה מה חסר בטענה.
לא. הגרף מורכב משני חלקים שאינם מחוברים. בכל משולש בנפרד יש מעגל, אבל אין דרך להגיע ממשולש אחד לשני במסלול רציף. בנוסף לזוגיות, צריך שכל הקשתות יהיו באותו חלק מחובר.
מוסיפים לגרף רחוב חדש בין צומת 2 לצומת 3. איזה מסלול אוילר יהיה אפשר למצוא לאחר ההוספה?
בתמונה מופיע הגרף לפני ההוספה.
מסלול פתוח בלבד, בין 1 ל־4
לפני ההוספה ארבעת הצמתים אי־זוגיים. ההוספה הופכת את הדרגות של 2 ו־3 מ־1 ל־2. הצמתים 1 ו־4 נשארים אי־זוגיים, ולכן יש מסלול פתוח ביניהם.
מוסיפים צומת חדש באמצע רחוב. האם מעגל האוילר נשמר?
בגרף המקורי יש מעגל אוילר. מסמנים צומת 5 באמצע הקשת 1–2 ומחליפים אותה בשתי קשתות: 1–5 ו־5–2. לא מוסיפים שום חיבור אחר. הסבירו מדוע התשובה נכונה גם בגרפים גדולים יותר.
כן. הדרגות של הצמתים הקיימים אינן משתנות, לצומת החדש דרגה 2 והגרף נשאר מחובר. אפשר גם לראות זאת במסלול עצמו: מחליפים את המעבר 1–2 במעבר 1–5–2, או בכיוון ההפוך. כך כל קשת בגרף החדש מופיעה בדיוק פעם אחת.
איך הופכים את המעגל למסלול פתוח אחרי הסרת קשת?
לפני שהסרנו את הקשת 2–3 היה מעגל: 1 → 2 → 3 → 4 → 5 → 3 → 1. בתמונה הגרף לאחר ההסרה. כתבו מסלול שעובר בכל הקשתות שנותרו בדיוק פעם אחת, והסבירו איך קיבלתם אותו מהמעגל.
מסלול אפשרי: 3–4–5–3–1–2, או הכיוון ההפוך. חותכים את המעגל במקום שבו הוסרה הקשת 2–3 ומתחילים מיד אחרי החתך. לא חייבים לשמור על נקודת ההתחלה הישנה. מתקבל מסלול רציף בין שני קצות הקשת שהוסרה.