מים, חשמל וגז, והקשר שלהם לגרפים מישוריים

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

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

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

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

נתחיל בתזכורת קצרה. גרף מתמטי (מהסוג שעליו אנחנו מדברים - לא זה שהוא שרטוט של פונקציה) הוא אוסף של צמתים, שמסומנים לרוב בנקודות או בעיגולים, וקשתות שמחברות חלק מזוגות הצמתים. באופן כללי גרף לא צריך להיות מתואר באמצעות ציור; מספיק לתאר אותו באמצעות קבוצת הצמתים (שיכולה פשוט להיות קבוצה של מספרים: “צומת מס’ 1”, “צומת מס’ 2” וכו’) וקבוצת הקשתות (“צומת 3 מחובר לצומת 5”…). כל גרף ניתן לצייר בהמוני דרכים שונות על נייר, בפרט אם לא דורשים שהקשתות יהיו קווים ישרים; הנה דוגמה לאותו גרף כשאנו מציירים אותו בשתי דרכים שונות:

מה שמעניין כאן הוא שבציור השמאלי, הקשתות של הגרף חותכות זו את זו (הקשת שמחברת את 2 עם 3 חותכת את הקשת שמחברת את 4 עם 1), אבל בציור הימני אף קשת לא חותכת אף קשת אחרת. מכאן אנו למדים שהתכונה “אם מציירים את הגרף על נייר, אין שתי קשתות שחותכות זו את זו” איננה טריוויאלית לחלוטין; יכולים להיות גרפים שהתיאור הרגיל שלהם על הנייר נראה מסובך ומלא חיתוכים פנימיים, אבל אפשר איכשהו לצייר אותם בלי שאף שתי קשתות יחתכו זו את זו. לגרף כזה, שניתן לצייר איכשהו על נייר דו ממדי (“מישור”) מבלי שאף שתי קשתות יחתכו זו את זו קוראים “גרף מישורי” (Planar Graph).

כעת יש לנו ניסוח טוב יותר של חידת המים-חשמל-גז: האם הגרף הבא הוא מישורי?

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

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

אם כן, הניסוח הסטנדרטי של המשפט המתמטי שהורג את חידת המים-חשמל-גז הוא “הגרף \( K_{3,3} \) איננו מישורי”. אביא כאן שתי הוכחות לטענה הזו; האחת ישירה למדי, וקרוב לודאי שכל ילד מסוגל להבין אותה. לרוע המזל, היא גם קרובה ככל שהדבר ניתן אל אותו שיקוץ שהמתמטיקאים מכנים “הוכחה באמצעות ציור”; הדרך היחידה לפרמל אותה בצורה שתשביע את רצונו של כל מתמטיקאי קפדן היא באמצעות שימוש במשפט כבד למדי - משפט עקומת ז'ורדן. משפט ז’ורדן אומר דבר מה שנראה טריוויאלי לחלוטין - שכל עקומה (לצורך העניין עקומה היא מה שמקבלים כששמים עיפרון על דף ומציירים בלי להרים את העיפרון מהדף) שלא חותכת את עצמה ושני קצותיה מתלכדים מחלקת את העולם (הדף שעליו ציירנו) ל”פנים” ו”חוץ”, ולא ניתן להגיע מהאחד לשני בלי לחתוך את העקומה בדרך. למרות שהמשפט נשמע טריוויאלי, הוכחתו מסובכת למדי. מצד אחד, זה נשמע אבסורדי. מצד שני, חשוב להבין שהמושג המדוייק של עקומה מוגדר בצורה יותר מורכבת ממה שהצגתי כאן (מה שהצגתי כאן לא ראוי להיקרא “הגדרה”), ולפורמליזם ולדיוק הזה יש מחיר.

הרעיון הבסיסי הוא זה: נסתכל על המעגל שנוצר מחיבור הקשתות 1-א’-2-ב’-3-ג’-1 (הקשת מ-1 אל א’; הקשת מא’ אל 2, וכו’). זה לא מעגל במובן הרגיל מגאומטריה, אלא פשוט מסלול בגרף שמתחיל ומסתיים באותו מקום. בכל צורה שבה נצייר את הגרף במישור, אוסף כל הקשתות הללו יתחום איזור כלשהו ויחלק אותו ל”פנים” ו”חוץ”. גם את זה כדאי להמחיש עם ציור:

נניח לרגע שהקשת שעוברת בין 1 לב’ עוברת בתוך ה”פנים” של המעגל; כפי שנראה בהמשך, ההנחה הזו לא פוגעת בהוכחה. אחרי שנעביר את הקשת נקבל את הדבר הבא:

מה קורה כעת עם הקשת א’-3? היא חייבת להימתח מחוץ לפנים המעגל; כי אם היא נמתחת בפנים, היא בהכרח תחתוך את הקשת 1-ב’. זה ברור מהציור, אבל גם פורמלית ניתן להראות זאת, בהסתמך על כך שהמעגל 1-ב’-3-ג’-1 מחלק את העולם ל”פנים” ו”חוץ” בעצמו, והנקודה א’ נמצאת ב”חוץ”, כך שקו שנמצא ב”פנים” ומגיע אל א’ חייב לעבור דרך קשתות המעגל בשלב מסויים.

אם כן, נמתח את הקשת בחוץ ונקבל משהו שכזה:

אבל כעת לא ניתן למתוח קו מ-2 אל ג’, מאותם נימוקים. אם מלכתחילה היינו מציירים את 1-ב’ בחוץ היינו “כולאים” צומת כלשהי בצורה דומה לכך שצומת מס’ 2 נכלאה, ולכן גם אז היינו מגיעים לסתירה.

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

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

שאלה מעניינת היא האם מספר הפאות של גרף נובעות מאופן הציור שלו, או שלא משנה איך נצייר אותו, תמיד נקבל אותו מספר פאות (כך שמספר הפאות הוא שמורה (invariant) של הגרף). התשובה היפה יותר, מבחינה מתמטית, היא השנייה; ואכן, מסתבר שכך הדבר, אבל טוב מכך - יש קשר פשוט להדהים בין מספר הפאות של הגרף ובין מספר הצמתים והקשתות שלו. אם הגרף קשיר (כלומר, יש מסלול מכל צומת לכל צומת אחר), בעל \( n \) צמתים, \( m \) קשתות ו-\( f \) פאות, אז מתקיים \( n-m+f=2 \). ההוכחה היא אינדוקטיבית על מספר הפאות, ואינה מסובכת במיוחד; אם יש רק פאה אחת, אז בהכרח הגרף הוא עץ, דהיינו גרף קשיר וחסר מעגלים (כי אחרת היה בו מעגל, ועל פי משפט ז’ורדן זה היה גורר שתי פאות), וידוע שבעץ מתקיים \( m=n-1 \); וכאשר יש לנו \( f+1 \) פאות אפשר לבחור קשת שנמצאת על מעגל, להסיר אותה, לקבל פאה אחת פחות (כי איחדנו שתי פאות) וקשת אחת פחות וגרף שעודנו קשיר, כך שניתן להשתמש עליו בהנחת האינדוקציה. ההכללה של הנוסחה לגרפים שאינם קשירים אינה מסובכת; חשבו על כך שכל גרף ניתן להציג כאיחוד זר של גרפים קשירים.

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

חזרה לגרף \( K_{3,3} \) האומלל. מכיוון שיש בו (קל לספור) \( n=6 \) צמתים ו-\( m=9 \) קשתות, נוסחת אוילר מראה לנו מייד שאם הוא מישורי, אז בכל ציור שלו במישור יהיו לו \( f=2+m-n=5 \) פאות. כעת נשים לב כי ניתן לספור את \( m \) באמצעות הפאות. אם \( p \) היא פאה כלשהי של הגרף, ו-\( d(p) \) הוא מספר הקשתות שנמצאות בפאה הזו (בתוכה או על השפה שלה), אז נקבל ש-\( m\ge\frac{1}{2}\sum d(p) \) כשהסכום נלקח על כל הפאות של הגרף; זאת מכיוון שאנו סופרים כל קשת לכל היותר פעמיים כי היא שייכת לכל היותר לשתי פאות (יש קשתות שנמצאות כולן בפאה אחת; לפעמים מסכימים לספור אותן פעמיים כדי שיתקבל שוויון מלא בנוסחה, אך אין לנו צורך בכך כאן).

כעת לפואנטה. בגרף שמכיל יותר מפאה אחת, כל פאה נקבעת באמצעות מעגל שיוצרות הקשתות שעל שפתה; אבל בגרף הדו צדדי, האורך המינימלי של מעגל הוא 4 (בדרך כלל הוא 3, אבל כאן זה בלתי אפשרי - מדוע?) ולכן \( d(p)\ge 4 \). לכן נקבל:

\( 9=m\ge\frac{1}{2}\sum d(p)\ge\frac{1}{2}\cdot f\cdot 4=2f=10 \)

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

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

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

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

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

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

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

ויקיפדיה האנגלית מביאה דוגמה נאה להמחשת שני המשפטים:

הגרף הזה נראה “כמעט” כמו \( K_{3,3} \), אבל הוא אינו מכיל כתת גרף לא את \( K_{3,3} \) ולא את \( K_5 \). מצד שני, הוא די בבירור התקבל מ-\( K_{3,3} \) על ידי הוספת הצומת B באמצע הקשת CF, כלומר הוא חלוקה של \( K_{3,3} \) ולכן על פי קורטובסקי הוא אינו מישורי; ואם נכווץ את הגרף על ידי כך שנאחד את B עם C (או את B עם F) נקבל את \( K_{3,3} \) ולכן על פי ווגנר הוא אינו מישורי.

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