גרף מישורי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
ייצוג גרפי של גרף מישורי

בתורת הגרפים, גרף מישורי הוא גרף שניתן לצייר במישור מבלי שהקשתות יחתכו זו את זו (חוץ מאשר בצומתי הגרף). לגרפים כאלה יש חשיבות מיוחדת באלגוריתמים הקשורים בראייה ממוחשבת וביישומים של תורת הגרפים בתעשייה, למשל לתכנון מעגלים חשמליים.

הגדרות פורמליות[עריכת קוד מקור | עריכה]

גרף מישורי הוא גרף שאפשר לשכן במישור. שיכון של גרף במישור הוא מודל גאומטרי שלו, שבו הצמתים הם נקודות במישור והקשתות הן עקומות שלא חותכות את עצמן או אף עקומה אחרת (חוץ מאשר בקודקודי הגרף). כל גרף ניתן לשיכון במרחב האוקלידי התלת-ממדי  \mathbb{R}^3 .

פאות של גרף משוכן במישור הן רכיבי הקשירות שנקבל במישור אם נסיר את הצלעות (האזורים שנתחמים על ידי הקשתות). האזור שמחוץ לצורה שיוצר הגרף הינו הפאה היחידה שאינה חסומה. מקובל לסמן את מספר הצמתים (vertices) של הגרף באות v, את מספר הקשתות (edges) ב- e, ואת מספר הפאות (faces) באות f.

נוסחת אוילר[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – נוסחת אוילר (תורת הגרפים)

גרף מישורי קשיר מקיים:

  • \ f = e - v+ 2

הוכחה: באינדוקציה על מספר הפאות, אם f = 1 אז אין בגרף מעגלים, לכן (הגרף קשיר) מדובר בעץ ומתקיים e = v - 1. אם f > 1 יש בגרף מעגל. כל קשת במעגל מהווה שפה לשתי פיאות בדיוק ואם נסיר אחת נקטין את מספר הקשתות והפאות באחת.

עבור גרף מישורי עם k רכיבי קשירות נכליל:

  • \ f = e - v + k + 1

הוכחה: (שימו לב שהפאה החיצונית משותפת לכל רכיבי הקשירות) 
f=\sum_{i=1}^{k}(e_i-v_i+2) - (k-1) = e-v+k+1

באופן כללי יותר, אם במקום לצייר את הגרף במישור מציירים אותו על-פני משטח קומפקטי כלשהו, הצירוף \ f-e+v הוא קבוע, השווה למאפיין אוילר של המשטח. לנוסחה זו יש גם פירוש הומולוגי.

אפיון של גרפים מישוריים[עריכת קוד מקור | עריכה]

הגרף K_5
הגרף K_{3,3}

הגרף השלם \ K_5 והגרף הדו-צדדי השלם \ K_{3,3} אינם מישוריים (ראו הוכחה להלן), ואם כך גם החלוקות שלהם אינן מישוריות. מתברר שזהו ההסבר היחיד לאי-מישוריות: כל גרף שאין לו תת-גרף שהוא חלוקה של אחד משני הגרפים הבעייתיים, הוא גרף מישורי. זהו תוכנו של משפט קורטובסקי (Kuratowsky). ניסוח שקול של התנאי שניתן בידי וגנר (Wagner) מדבר על מינורים של הגרף (גרפים המתקבלים מהגרף המקורי על ידי סדרה של מחיקת צמתים ואיחוד זוגות צמתים המחוברים בקשת) - גרף הוא מישורי אם אין לו מינור שהוא אחד משני הגרפים הבעייתיים.

משפט קורטובסקי הוא תוצאה אופיינית בתחום הנקרא Extermal graph theory, שבו 'מסבירים' מדוע גרף נכשל מלקיים תכונה מסוימת בכך שהוא מכיל אחד מבין מספר קטן של תת-גרפים בעייתיים. לדוגמה, אפשר לומר שגרף הוא k-מישורי אם אפשר לשכן אותו במישור, באופן שיש לכל היותר k חיתוכים בין קשתות (גרף 0-מישורי הוא גרף מישורי במובן שהוגדר לעיל). אז לכל k קיימת קבוצה סופית של גרפים 'אסורים', כך שכל גרף שאינו k-מישורי מכיל תת-גרף אסור.

תנאים הכרחיים למישוריות[עריכת קוד מקור | עריכה]

נציג כמה תנאים הכרחיים למישוריות, הנובעים משיקולים פשוטים יחסית.

  • משפט: בגרף מישורי  e\leq 3v -6

הוכחה: כל קשת גובלת בשתי פאות לכל היותר ופאה נתחמת על ידי שלוש קשתות לפחות, כלומר f\leq \frac{2e}{3} ויחד עם נוסחת אוילר יתקבל: \ e-v+2\leq \frac{2e}{3}.

  • מסקנה: הגרף השלם בן חמישה קודקודים \ K_5 אינו מישורי (\ e=10 \ v=5).
  • מסקנה נוספת: בגרף מישורי  \delta(G)\leq 5 כאשר \ \delta(G) הינו הדרגה המינימלית של קודקוד בגרף.

הוכחה: אחרת \ e=\frac{1}{2}\cdot \sum_{x\in V}^{}d(x) \geq \frac{6\cdot v}{2}=3\cdot v.

  • משפט: בגרף מישורי \ e\leq \frac{g}{g-2}\cdot(v-2) כאשר g הוא מותן הגרף (אורך המעגל הפשוט הקצר ביותר בגרף).

הוכחה: זהו חידוד של המשפט הקודם, כאשר הפעם כל פאה נתחמת על ידי g קשתות לפחות.

הוכחה נוספת לכך ש \ K_{3,3} אינו מישורי: נניח בשלילה ש \ K_{3,3} מישורי. לגרף 6 קודקודים ו9 צלעות. לפי נוסחת אוילר:

\ v - e + f = 2

לכן יש לגרף 5 פאות. לכל פאה יש לפחות שלוש צלעות, וכל צלע יכולה להשתתף בשתי פאות לפחות. מכאן:

\ \frac{2\,e}{5} = 3.6 מספר הצלעות הממוצע בכל פאה.

לכן חייבת להיות פאה עם לכל הפחות 3 צלעות ולכל היותר 3.6 צלעות - כלומר פאה בעלת 3 צלעות. קיבלנו סתירה מאחר ש \ K_{3,3} הינו גרף דו צדדי שלא מכיל משולשים מאחר שכל מעגליו באורך זוגי.

דוגמה לשימוש בתנאים למישוריות[עריכת קוד מקור | עריכה]

ניתן לפתור את הבעיה הגאומטרית: לכמה שטחים אפשר לחלק מעגל באמצעות פיזור n נקודות על פניו במרחקים שווים, וחיבור כל זוג נקודות בקו. כאשר אם \displaystyle n אי זוגי.

אם \displaystyle n אי-זוגי לא ייתכן שנחתכים יותר משני אלכסונים בנקודה. נתייחס לכל נקודת חיתוך כאל קודקוד. הגרף המתקבל הוא מישורי ומכאן מקיים את נוסחת אוילר. יש \displaystyle n קודקודים על שפת המעגל ו \displaystyle \binom{n}{4} קודקודים בתוך המעגל. (בין כל 2 צלעות זרות יש נקודת חיתוך) נשתמש בנוסחת אוילר:

\displaystyle f = e - n - \binom{n}{4} + 2

מספר הצלעות שווה לסכום הדרגות של כל הקודקודים לחלק ל - 2. על שפת המעגל דרגת כל קודקוד היא \displaystyle n-1 ובתוך המעגל - 4. ומכאן:


\displaystyle f = \frac{n(n-1) + 4\,\binom{n}{4}}{2} - n - \binom{n}{4} + 2

\displaystyle f = \binom{n}{2} + \binom{n}{4} + 1

גרפים מישוריים ומפות[עריכת קוד מקור | עריכה]

כשקרטוגרף מצייר מפה מדינית, הוא משתדל לצבוע מדינות שכנות בצבעים שונים, כדי להקל על ההבחנה ביניהן. הדרך הטבעית לחקור מצבים כאלה בתורת הגרפים היא להגדיר את הגרף הדואלי למפה, שבו הצמתים הם המדינות, וזוג צמתים מחוברים בקשת רק כאשר המדינות המתאימות שכנות זו לזו. מכיוון שהמפה המקורית היא מישורית (או כדורית, אם מדובר במפה כלל-עולמית), הגרף המתקבל הוא גרף מישורי.

המשימה של הגאוגרף היא לצבוע את צומתי הגרף, באופן שזוג צמתים מחוברים ייצבעו בצבעים שונים. משפט ארבעת הצבעים מבטיח שתמיד ניתן לעשות זאת בארבעה צבעים או פחות. בלשון אחרת, המשפט מבטיח שלכל גרף מישורי יש 4-צביעה.

קישורים חיצוניים[עריכת קוד מקור | עריכה]