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

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

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

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

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

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

pg1

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

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

pg2

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

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

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

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

pg3

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

pg4

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

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

pg5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17 תגובות על הפוסט “מים, חשמל וגז, והקשר שלהם לגרפים מישוריים

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

  2. לוצקי – שאלה מצויינת. באופן מפתיע התשובה היא "לא", וזהו בדיוק התוכן של משפט Fáry.
    למידע נוסף (כולל הוכחה, לפחות בערך) ניתן לפנות (כרגיל) לוויקיפדיה:
    http://en.wikipedia.org/wiki/F%C3%A1ry%27s_theorem

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

  3. עד כמה שאני מבין, זה בכל מקום – אי אפשר לדבר על פאות בלי להגדיר אותן פורמלית בתור רכיבי הקשירות השונים שנותרים אחרי שמוחקים את הגרף, ובלי ז'ורדן לא ברור בכלל למה יהיו כאלו (בפרט, טענה כמו "יש פאה בודדת אם ורק אם אין מעגל" נראית לי די דורשת את ז'ורדן; אולי אני טועה).

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

    קו ישר אופקי מחלק את המישור לשני חלקים! (רכיבי קשירות).

    המשפט הוא כמובן משפט הערך הממוצע של החשבון האינפיניטסימלי.

  5. אבחנה יפה מאוד, אני מסכים – אבל בכל זאת, ההוכחה של משפט ערך הביניים היא כן פשוטה. אפילו סטודנטים בסמסטר הראשון מבינים אותה (לפעמים…)

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

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר.