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