משפט אור

משפט אור הוא משפט בתורת הגרפים הקובע תנאי מספיק להוכחה כי גרף הוא המילטוני. כלומר אם גרף $G$ מקיים את תנאי המשפט, הרי ש-$G$ מכיל מעגל המילטוני.

המשפט הוכח בשנת 1960 על ידי המתמטיקאי הנורווגי אור אוסטיין (Øystein Ore, 1899 - 1968) ונחשב לאחת התרומות המשמעותיות שלו בכלל התחומים המתמטיים בהם עסק.

ניסוח פורמלי

לכל גרף פשוט G בעל $n\geq 3$ קודקודים, אם לכל שני קודקודים $x,y$ שאינם שכנים מתקיים $deg_{G}(x)+deg_{G}(y)\geq n$ אזי G גרף המילטוני.

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

הוכחה

נניח בשלילה כי המשפט אינו נכון. כלומר, קיים מספר טבעי $n$ וקיים גרף בעל $n$ קודקודים המפר את המשפט - כך שהגרף מקיים את תנאי המשפט שלכל שני קודקודים $x,y$ שאינם שכנים מתקיים $deg_{G}(x)+deg_{G}(y)\geq n$, אך הגרף אינו מכיל מעגל המילטוני (ולכן אינו המילטוני).

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

$G$ אינו גרף מלא (כיוון שאז היה המילטוני) ולכן נתסכל על שני קודקודים $s,t$ בגרף $G$ שאינם מחוברים על ידי קשת.

מהמקסימליות של $G$, נובע שיש מסלול המילטון $P=(s=v_{1},v_{2},...v_{n}=t)$ בין $s$ ל-$t$ בגרף (מכיוון שמתוך המקסימליות של $G$ נובע שהוספת קשת $st$ ל-$G$ יוצרת גרף המילטוני).

כיוון שהנחנו שמתקיים $deg_{G}(s)+deg_{G}(t)\geq n$, אזי ניתן להראות שקיים $2\leq i\leq n-1$ כך שמתקיים $sv_{i}\in E$ וגם $v_{i-1}t\in E$ (נוכיח קיום זה בסוף ההוכחה)

המחשה להוכחת משפט אור. בגרף ישנו מסלול המילטוני $s,...t$ אך אינו מכיל מעגל הימלטוני, לכל היותר יכולה להתקיים אחת הקשתות $sv_{i}$ או $tv_{i-1}$ (מסומנות בכחול). כיוון שאם שתיהן מתקיימות אזי הוספתן למסלול והסרת קשת $v_{i-1}v_{i}$ (מסומנת באדום) תיצור מעגל המילטוני.

אך זה גורר סתירה להנחה כי $G$ אינו המילטוני, כיוון שאז $G$ יכיל מעגל הילטוני $(s,v_{i},v_{i+1},...v_{n-1},t,v_{i-1},v_{i-2},...,v_{2},s)$, כפי שניתן לראות בהמחשה המצורפת.

כעת נוכיח כי בהכרח קיים $2\leq i\leq n-1$ כך שמתקיים $sv_{i}\in E$ וגם $v_{i-1}t\in E$ .

נסמן ב-$\Gamma (s)$ את אוסף השכנים של $s$ וב-$\Gamma (t)$, את אוסף השכנים של $t$, מכיוון ש-$s$ ו-$t$ אינם שכנים, אז $\Gamma (s),\Gamma (t)\subseteq \{v_{2},\ldots ,v_{n-1}\}$. נניח $\Gamma (s)=\{v_{i1},\ldots ,v_{ik}\}$ כאשר $i_{1}<\cdots <i_{k}$ ונגדיר $\Gamma ^{-}(s)=\left\{v_{i_{2}-1},\ldots ,v_{i_{k}-1}\right\}$. כלומר $\Gamma ^{-}(s)$ מכיל את כל הקודקודים שיש להם אינדקס הקטן ב-1 מאיזשהו קודקוד הנמצא ב-$\Gamma (s)$. שאיננו הקודקוד הראשון ב-$\Gamma (s)$ (שימו לב שב-$\Gamma (s)$ יש $k$ קודקודים ואילו $\Gamma ^{-}(s)$ יש רק $k-1$ קודקודים).

ברצוננו להראות ש-$\Gamma (t)\cap \Gamma ^{-}(s)\neq \emptyset$, כלומר שקיים קודקוד שכן ל-$t$ שהוא בעל האינדקס הנמוך ב-$1$ מצומת השכן ל-$s$.

נניח בשלילה ש-$\Gamma (t)\cap \Gamma ^{-}(s)=\emptyset$. על כן $\Gamma (t)$ מוכלת כולה בקבוצה $\{v_{2},\ldots ,v_{n-1}\}\setminus \Gamma ^{-}(s)$

זוהי קבוצה שגודלה $(n-2)-(k-1)=n-k-1$, זאת משום שכל איברי $\Gamma ^{-}(s)$ נמצאים בתוך $\{v_{2},\ldots ,v_{n-1}\}$ (זו הסיבה שלא כללנו ב-$\Gamma ^{-}(s)$ את הקודקוד $v_{i_{1}-1}$ שעלול היה להיות שווה ל-$v_{1}$). על כן $|\Gamma (t)|\leq n-k-1$, אבל אז:

$|\Gamma (s)|+|\Gamma (t)|\leq k+n-k-1=n-1\implies |\Gamma (s)|+|\Gamma (t)|=\deg(s)+\deg(t)\leq n-1$

בסתירה להנחתנו ש- $|\Gamma (s)|+|\Gamma (t)|=\deg _{G}(s)+\deg _{G}(t)\geq n$

לכן בהכרח קיים $2\leq i\leq n-1$ כך שמתקיים $sv_{i}\in E$ וגם $v_{i-1}t\in E$.

אי-אפשר לשפר את התנאי במשפט אור בדבר החסם התחתון על סכום הדרגות של קודקודים שאינם סמוכים. בפרט התנאי $deg_{G}(u)+deg_{G}(v)\geq n-1$ אינו מספיק כדי להבטיח את קיומו של מעגל המילטוני, למשל, ניקח שני עותקים של הגרף המלא על ${\frac {n-1}{2}}$ קודקודים, נבחר בכל אחד מהם קודקוד ונמזג את שני הקודקודים שנבחרו לקודקוד אחד. בגרף המתקבל, דרגת כל צומת היא לפחות ${\frac {n-1}{2}}$, ועל כן $deg_{G}(u)+deg_{G}(v)\geq n-1$ לכל שני צמתים אך הגרף הזה אינו המילטוני.

משפט דירק

משפט דירק (Dirac Andrew Gabriel, 1984-1925) הוא מקרה פרטי של משפט אור, הקבוע כי לכל גרף $G$ עם $n\geq 3$ קודקודים בו הדרגה המינימלית היא לפחות ${\frac {n}{2}}$ הוא בהכרח המילטוני.

הוכחה

נניח שב-$G$ כל צומת היא לפחות ${\frac {n}{2}}$, אז סכום הדרגות של שני הקודקודים לא שכנים הוא לפחות ${\frac {n}{2}}+{\frac {n}{2}}={\frac {2n}{2}}$, כך ש-${\frac {2n}{2}}=n\geq n$, כלומר $G$ מקיים את תנאי הדרגות במשפט אור ולכן בהכרח המילטוני.