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