גרף מישורי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
ניסוח (הורדתי את המילה קורטובסקי מתחילת ההבהרה). עדיין ברור שמדובר במשפט שלו לפי הכותרת. |
עריכה |
||
שורה 27:
באופן כללי יותר, אם במקום לצייר את הגרף במישור מציירים אותו על-פני משטח קומפקטי כלשהו, הצירוף <math>\ f-e+v</math> הוא קבוע, השווה ל[[מאפיין אוילר]] של המשטח. לנוסחה זו יש גם פירוש [[הומולוגיה (טופולוגיה אלגברית)|הומולוגי]].
== אפיון של גרפים מישוריים ==
== תנאים למישוריות ==▼
[[תמונה:the graph K5.jpeg|שמאל|ממוזער|150px|הגרף <math>K_5</math>]]▼
[[תמונה:the graph K33.jpeg|ימין|ממוזער|150px|הגרף <math>K_{3,3}</math>]]▼
ה[[גרף שלם|גרף השלם]] <math>\ K_5</math> וה[[גרף דו צדדי|גרף הדו-צדדי]] השלם <math>\ K_{3,3}</math> אינם מישוריים (ראו הוכחה להלן), ואם כך גם ה[[חלוקה (תורת הגרפים)|חלוקות]] שלהם אינן מישוריות. מתברר שזהו ההסבר היחיד לאי-מישוריות: כל גרף שאין לו תת-גרף שהוא חלוקה של אחד משני הגרפים הבעייתיים, הוא גרף מישורי. זהו תוכנו של משפט קורטובסקי (Kuratowsky). ניסוח שקול של התנאי שניתן בידי וגנר (Wagner) מדבר על מינורים של הגרף (גרפים המתקבלים מהגרף המקורי על ידי סדרה של מחיקת צמתים ואיחוד זוגות צמתים המחוברים בקשת) - גרף הוא מישורי אם אין לו מינור שהוא אחד משני הגרפים הבעייתיים.▼
▲=== תנאים הכרחיים למישוריות ===
נציג כמה תנאים הכרחיים למישוריות, הנובעים משיקולים פשוטים יחסית.
* '''משפט''': בגרף מישורי <math> e\leq 3v -6 </math>
הוכחה: כל קשת גובלת בשתי פאות לכל היותר ופאה נתחמת על ידי שלוש קשתות לפחות, כלומר <math>f\leq \frac{2e}{3}</math> ויחד עם נוסחת אוילר יתקבל: <math>\ e-v+2\leq \frac{2e}{3}</math>.
שורה 51 ⟵ 58:
לכן חייבת להיות פאה עם לכל הפחות 3 צלעות ולכל היותר 3.6 צלעות - כלומר פאה בעלת 3 צלעות.
קיבלנו סתירה מאחר ש <math>\ K_{3,3}</math> הינו גרף דו צדדי שלא מכיל משולשים מאחר שכל מעגליו באורך זוגי.
▲[[תמונה:the graph K5.jpeg|שמאל|ממוזער|150px|הגרף <math>K_5</math>]]
▲[[תמונה:the graph K33.jpeg|ימין|ממוזער|150px|הגרף <math>K_{3,3}</math>]]
▲ה[[גרף שלם|גרף השלם]] <math>\ K_5</math> וה[[גרף דו צדדי|גרף הדו-צדדי]] השלם <math>\ K_{3,3}</math> אינם מישוריים, ואם כך גם ה[[חלוקה (תורת הגרפים)|חלוקות]] שלהם אינן מישוריות. מתברר שזהו ההסבר היחיד לאי-מישוריות: כל גרף שאין לו תת-גרף שהוא חלוקה של אחד משני הגרפים הבעייתיים, הוא גרף מישורי. ניסוח שקול של התנאי שניתן בידי וגנר (Wagner) מדבר על מינורים של הגרף (גרפים המתקבלים מהגרף המקורי על ידי סדרה של מחיקת צמתים ואיחוד זוגות צמתים המחוברים בקשת) - גרף הוא מישורי אם אין לו מינור שהוא אחד משני הגרפים הבעייתיים.
▲זוהי תוצאה אופיינית בתחום הנקרא Extermal graph theory, שבו 'מסבירים' מדוע גרף נכשל מלקיים תכונה מסוימת בכך שהוא מכיל אחד מבין מספר קטן של תת-גרפים בעייתיים. לדוגמה, אפשר לומר שגרף הוא k-מישורי אם אפשר לשכן אותו במישור, באופן שיש לכל היותר k חיתוכים בין קשתות (גרף 0-מישורי הוא גרף מישורי במובן שהוגדר לעיל). אז לכל k קיימת [[קבוצה סופית]] של גרפים 'אסורים', כך שכל גרף שאינו k-מישורי מכיל תת-גרף אסור.
== דוגמה לשימוש בתנאים למישוריות ==
| |||