גרף מישורי

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

פאה של גרף משוכן היא אזור במישור שהקשתות מסביבתו מגדירות. הפאה החיצונית היא האזור שמחוץ לצורה הכללית. מסמנים v לצמתים, e לקשתות ו‑f לפאות.

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

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

שני גרפים בסיסיים שאינם מישוריים הם K5 (גרף של חמישה קודקודים שכל זוג מחובר) ו‑K_{3,3} (גרף דו‑צדדי עם שתי קבוצות של שלושה קודקודים, שכל זוג מקבוצות שונות מחובר). אם גרף מכיל תת‑גרף שהוא חלוקה של אחד מהשניים, הוא גם לא מישורי. זהו תוכן משפט קורטובסקי. יש נוסח שקול של וגנר שמדבר על מינורים, גזירות ואיחודים, ואומר שבדיקת מישוריות עברה למונחים של חוסר מינור אסור.

משפט קורטובסקי גם ממחיש רעיון כללי: תכונות שנשמרות כשמייצרים מינור מוסברות על ידי קבוצה סופית של גרפים 'אסורים'. לדוגמה, אפשר להגדיר k‑מישוריות כמספר החיתוכים המקסימלי המותר, ולכל k יש קבוצת גרפים אסורים משלו.

קיימים תנאים פשוטים שעוזרים לבדוק אם גרף לא מישורי. למשל, בכל גרף מישורי פשוט ומכיל יותר מ‑2 צמתים, מתקיימת אי־שוויון כללי e ≤ 3v - 6 (משמעותו: מספר הקשתות מוגבל ביחס לצמתים). תנאים כאלה מתקבלים מהעובדה שכל פאה תחומה לפחות על ידי שלוש קשתות ושכל קשת גובלת בשתי פאות לכל היותר.

דוגמה נוספת משתמשת בגרף K_{3,3} כדי להראות שהוא לא מישורי. בגרף זה v=6 ו‑e=9, ונוסחת אוילר נותנת f=5. אבל סכום המספרים של הקשתות סביב כל פאה לא מסתדר עם היעדר משולשים בגרף דו‑צדדי, ולכן יש סתירה.

שאלה גאומטרית טיפוסית: לכמה אזורים מחלקים מעגל אם מפזרים עליו n נקודות בשוויון מרחקים ומחברים כל זוג בניהם? נניח שהמסרק (החיבורים) חוצים זה את זה רק בנקודות חיתוך שאינם צמתים על השפה. אז כל נקודת חיתוך נחשבת לצומת פנימי, וסך הצמתים הכולל הוא n בצד החיצוני בתוספת
φ = C(n,4) צמתים פנימיים (קומבינציה של n ב‑4). לאחר חישוב דרגות הקודקודים והחלפתם בנוסחת אוילר מקבלים את הנוסחה המסכמת: f = C(n,2) + C(n,4) + 1.

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

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

פאה היא איזור בתוך הציור. יש אזור אחד גדול מחוץ לציור.

בשביל גרף שמחובר נכון: מספר הנקודות פחות מספר הקווים ועוד מספר האזורים שווה ל‑2. זו נוסחה פשוטה שמקשרת בין הנקודות, הקווים והאזורים.

יש שני ציורים חשובים שלא אפשרי לצייר בלי חיתוכים: K5 (חמישה נקודות שכל אחת מחוברת לכולן) ו‑K3,3 (שתי קבוצות של שלוש נקודות, כל נקודה בקבוצה מחוברת לכל נקודה בקבוצה השנייה). אם יש בגרף משהו מהצורות האלה, אי אפשר לציירו מישורי.

מחשבים כמה קווים אפשר שיהיו ביחס לנקודות. חשיבה כזו נותנת כללים שעוזרים לדעת מתי אי‑אפשר לצייר גרף בלי חיתוכים.

אם שים n נקודות על מעגל ומתחברים כל זוג, אז מספקים נקודות חיתוך פנימיות. בסוף מקבלים מספר אזורים שמתקבל מהנוסחה:
'מספר האזורים = מספר הזוגות של נקודות + מספר הרביעיות של נקודות + 1'.

מפה של מדינות הופכת לגרף: כל מדינה = נקודה, שכנות = קו. אם מצליחים לצבוע את הנקודות כך ששכנים שונים, זה כמו לצבוע מדינות. משפט ארבעת הצבעים אומר: תמיד יספיקו עד ארבעה צבעים.