משתמש:רועי/ארגז חול – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 1:
ב[[תורת הגרפים]], '''גרף מישורי''' הוא [[גרף]] שניתן לצייר ב[[מישור]] מבלי שהקשתות יחתכו זו את זו (חוץ מאשר בקודקודי הגרף). לגרפים כאלה יש חשיבות מיוחדת באלגוריתמים הקשורים ב[[ראיה ממוחשבת]] וביישומים של תורת הגרפים בתעשיה כמו תכנון
== הגדרות פורמליות ==
'''גרף מישורי''' הינו [[גרף]] הניתן לשיכון ב[[מישור]]. שיכון של גרף במישור הינו מודל גיאומטרי שלו בו הקודקודים הם נקודות על המישור והקשתות הן [[עקומה|עקומות]] שלא חותכות את עצמן או אף עקומה אחרת (חוץ מאשר בקודקודי הגרף). קל לראות שכל גרף ניתן לשיכון ב-<math> R^3 </math>; נוכל, למשל, לשכן את קודקודי הגרף על ציר אחד ולכל קשת נקצה מישור משלה.
'''פאות''' של גרף משוכן במישור הן רכיבי הקשירות שנקבל במישור אם נסיר את הצלעות (האיזורים שנתחמים על ידי הקשתות). כדאי לשים לב שהאיזור שמחוץ לצורה שיוצר הגרף הינו פיאה נוספת.
שורה 11:
== נוסחת אוילר ==
גרף מישורי קשיר מקיים:
* <math>\ f = m - n + 2 </math>
הוכחה: באינדוקציה על מספר הפאות, אם f = 1 אז אין בגרף מעגלים, לכן (הגרף קשיר) מדובר בעץ ו: m = n - 1. אם f > 1 יש בגרף מעגל. כל קשת במעגל מהווה שפה לשתי פיאות בדיוק ואם נסיר אחת נקטין את מספר הקשתות והפאות באחד.
עבור גרף מישורי עם k רכיבי קשירות נכליל:
* <math>\ f = m - n + k + 1 </math>
שכן הפאה החיצונית משותפת לכל רכיבי הקשירות.
== תנאים למישוריות ==
להלן כמה תנאים הכרחיים (ולא מספיקים) להיות גרף מישורי:
* '''משפט''': בגרף מישורי <math> m\leq 3n -6 </math>
* '''הוכחה''': כל
* '''מסקנה''' נוספת: <math> \delta(G)\leq 5 </math> כאשר <math>\ \delta(G) </math> הינו ה[[דרגה של קודקוד בגרף|דרגה]] המינימלית של קודקוד בגרף.
* '''הוכחה''': אחרת <math>m=\frac{1}{2}\cdot \sum_{v\in V}^{}d(v) \geq \frac{6\cdot n}{2}=3\cdot n</math>
* משפט קורטובסקי (kuratowsky): כל גרף שאינו מישורי מכיל [[תת גרף]] שאיזומורפי לחלוקה של <math>\ K_5</math> או <math>\ K_{3,3}</math>.▼
* '''משפט''': בגרף מישורי <math> m\leq \frac{g}{g-2}\cdot(n-2) </math> כאשר g הינו [[מותן של גרף|מותן הגרף]].
* '''הוכחה''': זהו חידוד של המשפט הקודם, כאשר הפעם כל פאה נתחמת על ידי g קשתות לפחות.
*'''מסקנה''': [[גרף דו צדדי|הגרף הדו צדדי]] השלם <math>\ K_{3,3}</math> אינו מישורי (שימו לב שהמותן שווה ל-4).
== משפט קורטובסקי (Kuratowsky)==
▲
▲יש שני גרפים מיוחדים שקל לראות כי אינם מישוריים: [[גרף שלם|הגרף השלם]] בן חמישה קודקודים <math>\ K_5</math>, ו[[גרף דו צדדי|הגרף הדו צדדי]] השלם <math>\ K_{3,3}</math>.
זוהי תוצאה אופיינית בתחום הנקרא Extermal graph theory, שבו 'מסבירים' מדוע גרף נכשל מלקיים תכונה מסויימת בכך שהוא מכיל אחד מבין מספר קטן של תת-גרפים בעייתיים. לדוגמא, אפשר לומר שגרף הוא k-מישורי אם אפשר לשכן אותו במישור, באופן שיש לכל היותר k חיתוכים בין קשתות (גרף 0-מישורי הוא גרף מישורי במובן שהוגדר לעיל). אז לכל k קיימת קבוצה סופית של גרפים 'אסורים', כך שכל גרף שאינו k-מישורי מכיל תת-גרף אסור.
שורה 46 ⟵ 49:
באופן כללי יותר, אם במקום לצייר את הגרף במישור מציירים אותו על-פני משטח קומפקטי כלשהו, הצירוף <math>\ F-E+V</math> הוא קבוע, השווה ל[[מאפיין אוילר]] של המשטח. לנוסחה זו יש גם פירוש [[הומולוגיה|הומולוגי]].
<!-- [[קטגוריה: תורת הגרפים]] -->
| |||