גרף מישורי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 61:
 
זוהי תוצאה אופיינית בתחום הנקרא Extermal graph theory, שבו 'מסבירים' מדוע גרף נכשל מלקיים תכונה מסוימת בכך שהוא מכיל אחד מבין מספר קטן של תת-גרפים בעייתיים. לדוגמה, אפשר לומר שגרף הוא k-מישורי אם אפשר לשכן אותו במישור, באופן שיש לכל היותר k חיתוכים בין קשתות (גרף 0-מישורי הוא גרף מישורי במובן שהוגדר לעיל). אז לכל k קיימת [[קבוצה סופית]] של גרפים 'אסורים', כך שכל גרף שאינו k-מישורי מכיל תת-גרף אסור.
 
 
== דוגמא לשימוש בתנאים למישוריות ==
ניתן לפתור את הבעיה הגיאומטרית: לכמה שטחים אפשר לחלק מעגל באמצעות פיזור n נקודות על פניו במרחקים שווים, וחיבור כל זוג נקודות בקו.
אם <math>\displaystyle n</math> אי-זוגי לא ייתכן שנחתכים יותר משני אלכסונים בנקודה. נתייחס לכל נקודת חיתוך כאל קודקוד. הגרף המתקבל הוא מישורי ומכאן מקיים את נוסחת אוילר. יש <math>\displaystyle n</math> קודקודים על שפת המעגל ו <math>\displaystyle \binom{n}{4}</math> קודקודים בתוך המעגל. (בין כל 2 צלעות זרות יש נקודת חיתוך) נשתמש בנוסחת אוילר:
 
<math>\displaystyle f = e - n - \binom{n}{4} + 2</math>
 
מספר הצלעות שווה לסכום הדרגות של כל הקודקודים לחלק ל - 2. על שפת המעגל דרגת כל קודקוד היא <math>\displaystyle n-1</math> ובתוך המעגל - 4.
ומכאן:
 
 
<math>\displaystyle f = \frac{n(n-1) + 4\,\binom{n}{4}}{2} - n - \binom{n}{4} + 2</math>
 
== גרפים מישוריים ומפות ==