גרף מישורי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
ניסוח (הורדתי את המילה קורטובסקי מתחילת ההבהרה). עדיין ברור שמדובר במשפט שלו לפי הכותרת. |
|||
שורה 56:
[[תמונה: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> אינם מישוריים, ואם כך גם ה[[חלוקה (תורת הגרפים)|חלוקות]] שלהם אינן מישוריות. מתברר שזהו ההסבר היחיד לאי-מישוריות:
זוהי תוצאה אופיינית בתחום הנקרא Extermal graph theory, שבו 'מסבירים' מדוע גרף נכשל מלקיים תכונה מסוימת בכך שהוא מכיל אחד מבין מספר קטן של תת-גרפים בעייתיים. לדוגמה, אפשר לומר שגרף הוא k-מישורי אם אפשר לשכן אותו במישור, באופן שיש לכל היותר k חיתוכים בין קשתות (גרף 0-מישורי הוא גרף מישורי במובן שהוגדר לעיל). אז לכל k קיימת [[קבוצה סופית]] של גרפים 'אסורים', כך שכל גרף שאינו k-מישורי מכיל תת-גרף אסור.
| |||