משפט מנטל

משפט מנטל בתורת הגרפים הוא משפט הקובע כי בהינתן גרף פשוט לא מכוון עם n צמתים וחסר משולשים (חסר מעגלים באורך 3), אז מספר הקשתות שלו הוא לכל היותר $\lfloor \frac{n^2}{4}\rfloor$. החסם אותו נותן משפט מנטל הדוק שכן הגרף הדו-צדדי המלא ($K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$) הוא חסר משולשים וכן מספר הקשתות שלו הוא $\lfloor \frac{n^2}{4}\rfloor$.

לפי הזהות $\alpha ⟹\beta \equiv ⌝\beta ⟹⌝\alpha$ נוכל לקבל ניסוח שקול למשפט הטוען כי אם בגרף G פשוט ולא מכוון יש יותר מ$\lfloor \frac{n^2}{4}\rfloor$ קשתות אז יש ב-G משולש.

משפט מנטל הוא מקרה פרטי של משפט טורן.

הגדרה פורמלית

יהי $G=<V,E>$ גרף, נסמן $|V|=n$, נניח כי לכל 3 צמתים $v_1,v_2,v_3\in V$ שונים בגרף, מתקיים $⌝(\{v_1,v_2\}\in E\wedge \{v_2,v_3\}\in E\wedge \{v_1,v_3\}\in E)$, אז $|E|\le \lfloor \frac{n^2}{4}\rfloor$

הוכחה

יהי $G=<V,E>$ גרף חסר משולשים. נבנה ממנו גרף דו-צדדי $G^{\prime }=<V,E^{\prime }>$ כך ש$|E|\le |E^{\prime }|\le \lfloor \frac{n^2}{4}\rfloor$ ,מה שיוכיח את המשפט, שכן גרף הוא דו צדדי אמ“ם אין בו מעגלים מאורך אי-זוגי, ובפרט באורך 3.

נסמן $v\in V$ הצומת בעל הדרגה המקסימלית. כמו כן, נסמן ב$S$ את $\{u\in V|\{v,u\}\in E\}$ (קבוצת השכנים). כעת נביט בגרף הדו-צדדי המלא $G^{\prime }=<V,E^{\prime }>$ על S ועל $V\setminus S$, נוכיח כעת כי $\mathrm{\forall }w\in V.de{g}_G(w)\le de{g}_{G^{\prime }}(w)$, ומנוסחת לחיצות היידים, נוכל להסיק כי $|E|\le |E^{\prime }|$, וזה יסיים את ההוכחה.

יהי $w\in V$, נחלק למקרים:

אם $w\notin S$, אז $de{g}_{G^{\prime }}(w)=|S|\ge de{g}_G(w)$ שכן $|S|$ היא הדרגה המקסימלית בגרף G, לפי הגדרת S .

אם $w\in S$, אז $de{g}_{G^{\prime }}(w)=|V\setminus S|\ge de{g}_G(w)$ מפני שגם בגרף G לא היו קשתות בין קודקודים S כיוון שG חסר משולשים (אם הייתה קשת בין $u_1,u_2\in S$ אז$v-u_1-u_2-v$ משולש בG). כמו כן $|E^{\prime }|\le \lfloor \frac{n^2}{4}\rfloor$ מפני שהמקרה גרוע ביותר הוא כאשר $|S|=\lfloor \frac{n}{2}\rfloor \wedge |V\setminus S|=\lceil \frac{n}{2}\rceil$ (שטח ריבוע הוא מקסימלי)

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] משפט מנטל32095908