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