מסלול אוילר
בתורת הגרפים, מסלול אוילר הוא מסלול בגרף העובר בכל קשת בו בדיוק פעם אחת. מעגל אוילר הוא מסלול אוילר מעגלי (מתחיל ונגמר באותו צומת). המסלול והמעגל נקראים על שם לאונרד אוילר שעסק בהם לראשונה כאשר פתר את בעיית הגשרים של קניגסברג.
אוילר הוכיח כי בגרף קשיר קיים מעגל אוילר אם ורק אם יש בדיוק 0 צמתים בעלי דרגה אי זוגית בגרף (כלומר, אין צומת שיוצא ממנו מספר אי זוגי של קשתות) וכי בגרף קיים מסלול אוילר אם ורק אם יש בדיוק 2 או 0 צמתים בעלי דרגה אי זוגית (במקרה של 0 צמתים בעלי דרגה אי זוגית מתקבל מעגל, משמע מעגל הוא מקרה פרטי של מסלול). בכל גרף עם מספר גדול יותר של צמתים בעלי דרגות אי זוגיות אין לא מסלול ולא מעגל אוילר (גרף סופי בעל צומת אחד בעל דרגה אי זוגית לא יכול להתקיים מלמת לחיצות הידיים). ההוכחה המלאה הראשונה לטענות אלה התפרסמה על ידי המתמטיקאי הגרמני קרל היירהולצר ב-1873 (לאחר מותו)[1].
מעגל אוילר: בגרף קשיר קיים מעגל אוילר אם ורק אם כל הדרגות זוגיות.
הוכחה: בהינתן גרף קשיר שדרגות כל צמתיו זוגיות, נראה איך למצוא מעגל אוילר. נצא מצומת כלשהו ונתקדם בגרף באופן שרירותי, ללא חזרה על קשתות, עד אשר "נתקע", כלומר נגיע לצומת שאי אפשר לבחור ממנו קשת שעדיין לא נבחרה. הטענה היא שזה יקרה רק כשנחזור לצומת שממנו התחלנו. הסיבה היא שבכל שלב בבחירת המסלול, פרט לצומת ההתחלה והסיום במסלול הנבחר, לכל שאר הצמתים דרגה זוגית במסלול - מכיוון שעל כל כניסה לצומת יש יציאה ממנו. אם נכנס לצומת כשסך כל דרגתו במסלול היא אי זוגית, הרי אי אפשר להתקע, כי מזוגיות הדרגה נובע כי תהיה קשת שעדיין לא השתמשנו בה. לכן המסלול נתקע רק אם חוזרים לנקודת הפתיחה, כי זו הדרך היחידה שדרגת הצומת בסוף המסלול יכולה להיות זוגית. כעת נסתכל על תת-הגרף המתקבל מהקשתות שעדיין לא כוסו. בתת-הגרף הזה הדרגה בכל צומת היא זוגית, מכיוון שמהקשתות שהורדנו היה מספר זוגי בכל צומת. נבחר צומת כלשהו על המסלול שכבר סימנו, שיוצאות ממנו קשתות שטרם נבחרו (חייבות להיות כאלה, אחרת הגרף אינו קשיר), ונחפש מעגל שמתחיל ונגמר באותו צומת. אם נתקעים גם במקרה זה, ממשיכים לחפש "תיקון", בדרך רקורסיבית. משמצאנו מעגל אוילר, ניתן להוסיף אותו למסלול המקורי שלנו - במקום שנמשיך בקשת שבחרנו מלכתחילה, נכנס קודם למעגל החדש שבנינו, ואחרי שנסיים לעבור בו נחזור לצומת שממנה התחלנו, ואפשר להמשיך משם כרגיל במסלול המקורי שלנו.
נניח שקיים מעגל אוילר. מכיוון שזהו מעגל, המסלול לא מסתיים באף קודקוד. לכן מספר הכניסות והיציאות מכל קודקוד שווה. כתוצאה מכך שהמסלול עובר על כל צלע פעם אחת ויחידה מספר הכניסות והיציאות שווה ממש לדרגת הקודקוד. נניח שיש כניסות בקודקוד מסוים, מכאן יש יציאות, ולכן דרגת הקודקוד היא . מכיוון ש- מספר טבעי, קבלנו דרגה זוגית.
מסלול אוילר: בגרף קשיר לא מכוון יש מסלול אוילר אם ורק אם יש בו 0 או 2 קודקודים עם דרגה אי זוגית.
הוכחה: נניח שקיימים רק 2 קודקודים עם דרגה אי-זוגית: a,b. נוסיף לגרף קודקוד c שממנו יוצאות שתי צלעות, אחת ל-a והשנייה ל-b. אנו עומדים בתנאי המשפט למעלה, לכן קיים מעגל אוילר המתחיל ומסתיים בקודקוד c. נשמיט את הקודקוד c ונשאר לנו מסלול אוילר בין a ל b.
נניח שקיים מסלול אוילר. אם תחילת המסלול וסופו חלים באותו קודקוד - זהו מעגל אוילר, ולכן יש 0 קודקודים אי זוגיים. נחבר את תחילתו וסופו ונקבל מעגל אוילר ולכן כל דרגות הקודקודים זוגיות. נשמיט את הצלע - יש לנו 2 קודקודים שדרגתם אי זוגית.
תכונות גרף אוילרי: אם בגרף קשיר d-רגולרי (דרגת כל צומת בו היא בדיוק d) כמות הצמתים היא אי זוגית, אזי d חייב להיות זוגי, שכן סכום הדרגות של הצמתים בגרף הוא תמיד זוגי (כל קשת תורמת שתי דרגות בדיוק) ועל כן גרף זה הוא אוילרי בהכרח, שאם לא כן, הרי שלא היה קשיר.
גרפים מכוונים: בגרף מכוון תנאי הכרחי ומספיק לקיום מעגל אוילר הוא שהגרף יהיה קשיר היטב ובכל קודקוד דרגת הכניסה זהה לדרגת היציאה. בגרף מכוון יש אלגוריתם פולינומי לספירת מעגלי אוילר, תוך שימוש במשפט קירכהוף, אולם בגרף לא מכוון הבעיה היא שלמה ל#P (כלומר בדומה לבעיית השידוך המושלם בגרף, זהו מקרה שבו בעיית ההכרעה היא בP אולם בעיית הספירה קשה)[2].
ראו גם
[עריכת קוד מקור | עריכה]קישורים חיצוניים
[עריכת קוד מקור | עריכה]
- גדי אלכסנדרוביץ', איך אוילר עוזר לנו לבנות בתים ולטייל על גשרים, באתר "לא מדויק", 6 במאי 2008
- מסלול אוילר, באתר MathWorld (באנגלית)
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ Early Writings on Graph Theory: Euler Circuits and The K¨onigsberg Bridge Problem
- ^ Graham Brightwell, Peter Winkler: Counting Eulerian Circuits is #P-Complete. ALENEX/ANALCO 2005:259-262