נוסחת אוילר (תורת הגרפים)

נוסחת אוילר היא נוסחה מרכזית בתורת הגרפים שפיתח לאונרד אוילר. על פי הנוסחה, עבור גרפים מישוריים קשירים, ישנו קשר בין מספר הקשתות $e$, מספר הצמתים $v$, ומספר הפאות $f$, כאשר גם השטח שמסביב לגרף נספר בתור פאה:

דוגמה של גרף מישורי: מספר הצמתים 8, מספר הקשתות 14, מספר הפאות 8, ואכן 8=14-8+2

$\ f=e-v+2$

בזכות נוסחת אוילר, מאפיין אוילר של המישור קשור מוגדר היטב ושווה לביטוי $\chi =v-e+f=2\,\!$.

ניתן להכליל את הנוסחה על ידי השמטת הדרישה שהגרף קשיר, ואז יתקיים:

$\ f=e-v+c+1$

כאשר $c$ הוא מספר רכיבי הקשירות.

הוכחת הנוסחה

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

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

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

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

הוכחת קושי

הוכחה זו ניתנה על ידי קושי ב-1811 והיא מוכיחה כי מאפיין אוילר עבור פאונים אפלטוניים או במישור דו-ממדי הוא 2. הוכחה זו מראה כי הנוסחה של אוילר עובדת לכל פאון קמור, ובאופן כללי יותר לכל פאון שהגבול שלו הוא שקול טופולוגית לספירה ושהשטחים שלו שקולים טופולוגית לדיסק.

יהי פאון אשר פאה אחת שלו מופנית כלפי מעלה. נסיר פאה זו כך שהקודקודים והמקצועות הסמוכים לו נשארים במקום וכעת יש לנו "קופסה" פתוחה. נמתח את הקופסה הפתוחה ככה שהקודקודים בפתח הפאון יקיפו (על משטח דו־ממדי) את כל שאר הקודקודים ובכך יצרנו גרף של קודקודים ומקצועות (בעצם, מקצועותיו של הפיאון הן הקשתות של הגרף) ולכן גם שטח בין קשתות אלו (כלומר האזורים שהיו הפיאות של הפאון) נוצר גם הוא. לשטחים הללו נקרא שטחי הגרף (להלן איור א'). לכל שטח הכלוא בין קשתות נקרא שטח גרף פנימי. לאזור שמחוץ לגרף נקרא שטח גרף חיצוני. נתייחס לשטח האחרון כפאה שהסרנו בהתחלה. ביצירת גרף אין אנחנו מסירים או מוסיפים ישר או קודקוד ולכן מספר הקודקודים $V$ בגרף, (vertices), זהה למספר הקודקודים של הפאון. כמו כן מספר הקשתות $E$, (edges), זהה גם הוא. נסמן $F$, (face), את מספר השטחים הכלואים בין ישרים בגרף + שטח הגרף החיצוני. סכום שטחים אלה זהה לסכום פיאות הפאון (להלן איור ב').

(ב') רשת קודקודים, ישרים ושטחים עבור מקרה של קובייה.

המרת הגרף

3 צעדים יבוצעו על הגרף שלנו:

1. אם לשטח גרף פנימי יש יותר מ3 צדדים, נעביר מיתר מקודקוד מסוים לקודקוד שאינו מחובר אליו כבר בקשת (להלן איור ג'). נבחין כי עבור צעד בודד מספר הקודקודים לא השתנה, התווספו שטח אחד וקשת אחת. לכן $V-E+F\Longleftarrow V-E-1+F+1\Longleftarrow V-(E+1)+(F+1)\Longleftarrow V-E+F$ והביטוי לא השתנה.
   

   

   (ג') המחשת תהליך שלב 1 עד להשגת הרשת מורכבת ממשולשים.

2. כעת אם לאחד המשולשים קיימת קשת משותפת עם שטח הגרף החיצוני, אז נסיר אותו. נבחין כי עבור צעד בודד מספר הקודקודים לא השתנה, החסרנו שטח אחד והחסרנו קשת אחת. לכן $V-E+F\Longleftarrow V-E+1+F-1\Longleftarrow V-(E-1)+(F-1)\Longleftarrow V-E+F$ והביטוי לא השתנה.
   
3. כעת אם לאחד המשולשים יש שתי קשתות משותפות לשטח הגרף החיצוני, נסיר אותו. נבחין כי עבור צעד אחד החסרנו קודקוד אחד, שטח אחד ושתי קשתות. לכן$V-E+F\Longleftarrow V-1-E+2+F-1\Longleftarrow (V-1)-(E-2)+(F-1)\Longleftarrow V-E+F$ והביטוי לא השתנה.

נציין שצעד 1 יבוצע עד הסוף עוד לפני צעד 2 וצעד 3. כלומר עד שכל שטח גרף פנימי יהיה משולש (איור ג'). כאשר אפשרי, צעד 3 תמיד יבוצע לפני צעד 2 (איור ד'). בסוף תהליך זה נקבל משולש אחד ויחיד. ועבורו מתקיים: $V-E+F=3-3+2=2$. מאחר שלאורך כל התהליך הביטוי $V-E+F$ נשאר זהה ומתקיים עבור הגרף, הוא מתקיים אז בווודאי עבור הפאון ומקיים $V-E+F=2$.

$QED$

(ד') המחשה של צעדים 2 ו3 מבוצעים. כאשר צעד 3 אפשרי, הוא יבוצע שוב ושוב עד להשגת משולש בודד.

נוסחת אוילר לפאונים

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

מנוסחת אוילר אפשר להסיק את המיון של הפאונים האפלטוניים, שהם פאונים שבהם כל הפאות חופפות לאותו מצולע משוכלל (נאמר, בן n צלעות), ובכל קודקוד נפגש אותו מספר פאות (נאמר, m). אם f הוא מספר הפאות, אז מספר הצלעות שווה ל-$e=f\cdot n/2$, ומספר הקודקודים הוא $v=f\cdot n/m$. על פי נוסחת אוילר $\ f+f\cdot {\frac {n}{m}}=f\cdot {\frac {n}{2}}+2$, כלומר $\ f={\frac {4m}{2m-(m-2)n}}$, וזה צריך להיות כמובן מספר טבעי. כאשר מוסיפים את הדרישה $\ n,m\geq 2$, מתקבלים למשוואה הדיופנטית הזו רק חמישה פתרונות.

ראו גם

• מאפיין אוילר של משטח

קישורים חיצוניים

• גדי אלכסנדרוביץ', הגופים האפלטוניים, נוסחת אוילר לפאונים, וכדורגל, באתר "לא מדויק", 31 בינואר 2010
• גדי אלכסנדרוביץ', הוכחה לנוסחת אוילר לגרפים בעזרת גרפים אוילריים, באתר "לא מדויק", 30 באפריל 2019
• נוסחת אוילר, באתר MathWorld (באנגלית)
• אביגייל קירק, Euler's polyhedron formula, באתר "Plus" ביוני 2007