מסלול אוילריאני

מתוך ויקיפדיה, האנציקלופדיה החופשית

הגדל

בתורת הגרפים, מסלול אוילריאני הוא מסלול בגרף העובר בכל קשת בגרף בדיוק פעם אחת. מעגל אוילריאני הוא מסלול אוילריאני המתחיל ונגמר באותו צומת. המסלול והמעגל נקראים על שם לאונרד אוילר שעסק בהם לראשונה כאשר פתר את בעיית הגשרים של קניגסברג.

אוילר הוכיח כי בגרף קיים מעגל אוילריאני אם ורק אם יש בדיוק 0 צמתים בעלי דרגה אי זוגית בגרף (כלומר, אין צומת שיוצא ממנו מספר אי זוגי של קשתות) וכי בגרף קיים מסלול אוילריאני אם יש בדיוק 2 צמתים בעלי דרגה אי זוגית. בכל גרף עם מספר גדול יותר של צמתים בעלי דרגות אי זוגיות אין לא מסלול ולא מעגל אוילריאני (גרף בעל צומת אחד בעל דרגה אי זוגית לא יכול להתקיים).

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

[עריכה] ראו גם

שפות אחרות