משתמש:רועי/ארגז חול – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 16:
== נוסחת הפאון של אוילר ==
גרף מישורי קשיר מקיים:
* <math> f = m - n + 2 </math> הוכחה: באינדוקציה על מספר הפאות, אם f = 1 אז אין בגרף מעגלים, לכן (הגרף קשיר) מדובר בעץ ו: m = n - 1. אם f > 1 יש בגרף מעגל. כל צלע במעגל מהווה שפה לשתי פיאות בדיוק ואם נסיר אותה נקטין את מספר הקשתות והפאות באחד.
עבור גרף מישורי עם k רכיבי קשירות נכליל:
* <math> f = m - n + 1 + k </math> שכן הפאה החיצונית משותפת לכל רכיבי הקשירות ולכן כל רכיב קשירות נוסף מקטין את מספר הפאות
== תנאים למישוריות ==
* <math> m\leq 3n -6 </math>
* <math> m\leq \frac{g}{g-2}\cdot(n-2) </math>
* <math> \delta(G)\leq 5 </math>
* משפט קורטובסקי (kuratowsky): כל גרף שאינו מישורי מכיל [[תת גרף]] שאיזומורפי לחלוקה של <math>\ K_5</math> או <math>\ K_{3,3}</math>.
▲שכן הפאה החיצונית משותפת לכל רכיבי הקשירות ולכן כל רכיב קשירות נוסף מקטין את מספר הפאות בנוסחה באחד.
== אפיון של גרפים מישוריים ==
| |||