החוקים של המשחק

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

 

 

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

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

כדי לפרמל את הבעיה הזאת בצורה מתמטית, ולראות למה היא לא פתירה, נתחיל עם אחד המבנים הבסיסיים במתמטיקה – הגרף. הגרף המתמטי הוא פשוט אוסף של צמתים (נקודות) וקשתות שיכולות לחבר זוגות של צמתים. למשל, בכפר שלנו מלמעלה, יש שלושה בתים ושלושה מקורות למים, חשמל ואינטרנט, שנותנים לנו סה"כ 6 צמתים, ואנחנו רוצים לבנות סה"כ \( 3 \times 3 = 9\) חיבורים או קשתות. כאשר לא אכפת לנו שהקשתות חותכות אחת את השנייה, נקבל גרף שנראה ככה:

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

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

איך בודקים אם גרף הוא מישורי?

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

בגרף הזה יש 7 קודקודים, 9 קשתות ו 4 תחומים במישור, שמופרדים ע"י הקשתות.

איך המספרים האלו משתנים כאשר מורידים קשת מהגרף, נניח קשת 2-3 ? במקרה הזה, התחומים A ו D יתמזגו לתחום אחד, ובעצם "ימחקו" את אחד מ 4 התחומים שהתחלנו איתם. בצורה דומה, אם נסיר את הקשת 3-4, אז תחומים A ו B יתמזגו לתחום אחד.

מצד שני, אם נוסיף קשת, נניח 5-6, אז תחום C יתפצל לשני תחומים ואז יהיו סה"כ 5 תחומים. סה"כ, אנחנו רואים שהורדת קשת אחת גורמת להורדת תחום אחד, והוספת קשת מוסיפה תחום. התבנית הזאת נכונה כמעט תמיד, אבל יש מקרים יוצאי דופן. למשל, אם נסיר את קשת 1-2, אז התחום משני הצדדים שלה הוא D, ולכן ההסרה שלה לא תמזג שני תחומים שונים. אבל, אם נחשוב לרגע מה קרה פה, אז נראה שבעצם הסרת הקשת הזאת שוברת משהו פנימי בגרף – הקשירות שלו. גרף נקרא קשיר אם בין כל שני צמתים יש מסלול של קשתות שמחבר בינהן. במקרה שבו מסירים את הקשת 1-2 הגרף המתקבל יהיה לא קשיר כי אין דרך אחרת להגיע מצומת 1 לצומת 2. סה"כ, נראה כאילו כל עוד אנחנו מוסיפים או מורידים קשתות בלי לפגוע בקשירות של הגרף, זה תמיד יוריד או יוסיף תחום בהתאם.

הטיעון למעלה פחות או יותר מרמז שעבור הוספה והורדה של קשתות, שלא פוגעת בקשירות, מספר הקשתות \(E\) פחות מספר התחומים \(F\) נשאר קבוע. במקרה שלנו הקבוע הזה יהיה \(E-F=9-4=5\). אם נשחק עם קצת גרפים קשירים אחרים, נקבל שההפרש הזה הוא בדיוק מספר הצמתים \(V\) פחות 2. זה מוביל לנוסחא מאוד חשובה שנקראת המציין של אוילר שאומרת:

\(V-E+F=2\)

הנוסחא הזאת נכונה לכל גרף קשיר מישורי, והיא מראה לנו את הקשר בין מספר הצמתים, קשתות ותחומים של הגרף. יותר מכך, נשים לב ש V סור את מספר האובייקטים ה "0-מימדיים" (צמתים), E סופר את האובייקטים ה "1-מימדיים" (קשתות) ו F סופר את האובייקטים ה "2-מימדיים" (תחומים).

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

הגרף \(K_{3,3}\) הוא לא מישורי

בגרף \(K_{3,3}\) יש \(V=6\) צמתים ו \(E=3\times 3=9\) קשתות. כמה תחומים יהיו בו אם הוא היה מישורי?

שימוש במציין אויילר יראה לנו שיהיו \(F=2+E-V=2+9-6=5\) תחומים. אבל, המבנה של הגרף מכיל יותר מרק כמות הצמתים והקשתות. האם נוכל להשתמש בו כדי למצוא אינופרמציה נוספת על מספר התחומים?

לדוגמא, בואו נסתכל שוב על הגרף

אפשר להגדיר כל תחום ע"י המסלול שסובב אותו נגד כיוון השעון. למשל בדוגמא למעלה נקבל את התחומים:

• A: 2->4->3->2
• B: 3->4->7->6->3
• C: 3->6->7->5->3
• D: 1->2->3->5->7->4->2->1

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

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

אם נספור את כל הקשתות שצריך כדי להקיף את כל התחומים, נקבל לפחות \(4\times F\) קשתות. אבל, נשים לב שכל קשת נספרת פעמיים בדיוק (למשל בדוגמא למעלה הקשת 3-4 נספרת פעם בסיבוב סביב A ופעם סביב B). לכן בעצם נקבל ש \(9=E \geq 2\times F\). אבל, כבר ראינו ש \(F=5\) , מה שמוביל אותנו לסתירה ש \(9\geq 2\times 5=10\). לכן, נסיק שההנחה שלנו הייתה שגויה, כלומר \(K_{3,3}\) לא יכול להיות מישורי.

אז מתי גרף כלשהו הוא מישורי?

ראינו שלא ניתן לצייר את \(K_{3,3}\) במישור השטוח. האם יש עוד גרפים שהם לא מישוריים?

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

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

כאשר עוזבים את העולם השטוח

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

מה בקשר למשטחים אחרים? בצורה מפתיעה, כן ניתן לצייר את \(K_{3,3}\) בלי חיתוכים של קשתות על הטורוס (=סופגנייה):

בדיוק כמו במישור, גם שם קיים מציין אויילר, רק שבטורוס הנוסחא היא \(V-E+F=0\).

אם היינו מנסים לכתוב מחדש את ה"הוכחה" מלמעלה, אז נקבל שמספר התחומים הוא \(F=E-V=9-6=3\), והפעם \(9=E\geq 2\times F=6\) ולכן לא נקבל סתירה כמו הנסיון לצייר את הגרף במישור.

מה קורה עם משטחים אחרים? אתם מוזמנים לנסות ליצור משטחים חדשים ולבדוק באיזה מהם אפשר לצייר את \(K_{3,3}\) .

איפה אפשר ללמוד עוד?

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