גרף מישורי

ייצוג גרפי של גרף מישורי

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

הגדרות פורמליות

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

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

נוסחת אוילר

ערך מורחב – נוסחת אוילר (תורת הגרפים)

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

• $\ 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) מדבר על מינורים של הגרף (גרפים המתקבלים מהגרף המקורי על ידי סדרה של מחיקת צמתים ואיחוד זוגות צמתים המחוברים בקשת) - גרף הוא מישורי אם אין לו מינור שהוא אחד משני הגרפים הבעייתיים.

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

תנאים הכרחיים למישוריות

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

• משפט: בגרף מישורי פשוט וקשיר בעל $v\geq 3$ מתקיים $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}$ אינו מישורי (כאן המותן שווה ל-4).

הוכחה נוספת לכך ש $\ 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-צביעה.

קישורים חיצוניים

מדיה וקבצים בנושא גרף מישורי בוויקישיתוף

• גדי אלכסנדרוביץ', מים, חשמל וגז, והקשר שלהם לגרפים מישוריים, באתר "לא מדויק", 29 בספטמבר 2008
• גרף מישורי, באתר MathWorld (באנגלית)