מסלול אוילר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ תקלדה |
||
שורה 9:
הוכחה: בהנתן גרף קשיר שדרגות כל צמתיו זוגיות, נראה איך למצוא מעגל אוילר. נצא מצומת כלשהו ונתקדם בגרף באופן שרירותי, ללא חזרה על קשתות, עד אשר "נתקע", כלומר נגיע לצומת שאי אפשר לבחור ממנו קשת שעדיין לא נבחרה. הטענה היא שזה יקרה רק כשנחזור לצומת שממנו התחלנו. הסיבה היא שבכל שלב בבחירת המסלול, פרט לצומת ההתחלה והסיום במסלול הנבחר, לכל שאר הצמתים דרגה זוגית במסלול - מכיון שעל כל כניסה לצומת יש יציאה ממנו. אם נכנס לצומת כשסך כל דרגתו במסלול היא אי זוגית, הרי אי אפשר להתקע, כי מזוגיות הדרגה נובע כי תהיה קשת שעדיין לא השתמשנו בה. לכן המסלול נתקע רק אם חוזרים לנקודת הפתיחה, כי זו הדרך היחידה שדרגת הצומת בסוף המסלול יכולה להיות זוגית. כעת נסתכל על תת הגרף המתקבל מהקשתות שעדיין לא על כוסו. בתת הגרף הזה הדרגה בכל צומת היא זוגית, מכיון שמהקשתות שהורדנו היה מספר זוגי בכל צומת. נבחר צומת כלשהו על המסלול שכבר סימנו, שיוצאות ממנו קשתות שטרם נבחרו (חייבות להיות כאלה, אחרת הגרף אינו קשיר), ונחפש מעגל שמתחיל ונגמר באותו צומת. אם נתקעים גם במקרה זה, ממשיכים לחפש "תיקון", בדרך [[רקורסיה|רקורסיבית]]. משמצאנו מעגל אוילרי, ניתן להוסיף אותו למסלול המקורי שלנו - במקום שנמשיך בקשת שבחרנו מלכתחילה, נכנס קודם למעגל החדש שבנינו, ואחרי שנסיים לעבור בו נחזור לצומת שממנה התחלנו, ואפשר להמשיך משם כרגיל במסלול המקורי שלנו.
נניח וקיים מעגל אוילר. מאחר שזהו מעגל, המסלול לא מסתיים באף קודקוד. לכן מספר הכניסות והיציאות מכל קודקוד שווה. מאחר שהמסלול ועובר על כל צלע פעם אחת ויחידה מספר הכניסות והיציאות שווה ממש לדרגת הקודקוד. נניח שהיו <math>x</math> כניסות בקודקוד מסוים, מכאן היו <math>x</math> יציאות,
'''מסלול אוילר:''' בגרף קשיר לא מכוון יש מסלול אוילר אם ורק אם יש בו 0 או 2 קודקודים עם דרגה אי זוגית.
| |||