משפט ארבעת הצבעים
מתוך ויקיפדיה, האנציקלופדיה החופשית
משפט ארבעת הצבעים הוא תוצאה בולטת בהיסטוריה של הטופולוגיה הקומבינטורית ושל תורת הגרפים. לפי המשפט, אפשר לצבוע כל מפה מדינית, באופן שכל שתי מדינות בעלות קו גבול משותף נצבעות בצבע שונה, תוך שימוש בארבעה צבעים בלבד. מתמטיקאים החלו לחקור את הבעיה באמצע המאה התשע-עשרה. היא נודעה כ'השערת ארבעת הצבעים', וזכתה ל'הוכחות' שגויות רבות.
בניסוח מודרני, המשפט מבטיח שלכל גרף מישורי קיימת צביעת קודקודים בארבעה צבעים. אנשי תורת הגרפים מכירים הוכחות קלות יחסית לכך שקיימת צביעה בחמישה צבעים, אבל ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב- 1976, והיא כרוכה בחיפוש ממוחשב על-פני אלפי מקרים. זו הייתה ההשערה המפורסמת הראשונה שהוכחה בעזרת מחשב, ובתחילה לא הייתה הסכמה כללית על תקפות ההוכחה, בעיקר בנימוק שלא הוכחה נכונותן של תוכניות המחשב עצמן. מאז נעשו נסיונות רבים למצוא הוכחה סטנדרטית יותר, שיכולה לעמוד לבקורת עמיתים, אבל הוכחה כזו עדיין לא נמצאה.
האיור משמאל מציג מפה סכמטית של ארבע מדינות, שלכל אחת מהן יש גבול משותף עם כל האחרות. לכן לא ניתן לצבוע אותה בפחות מארבעה צבעים.
תוכן עניינים |
[עריכה] מפות וגרפים
הקשר בין מפות מישוריות לבין גרפים מישוריים מבוסס על בנית הגרף הדואלי, שהיא בניה סטנדרטית בתורת הגרפים. בגרף המתאים למפה נתונה, כל מדינה מיוצגת על-ידי צומת, וכל שתי מדינות שלהן יש גבול משותף מחוברות בקשת בין שני הצמתים המתאימים. משמאל מוצגת דוגמה למפה ולגרף המתאים לה.
כעת, צביעת המדינות על המפה שקולה לבחירת צבע בכל קודקוד, באופן כזה שלשני קודקודים המחוברים בקשת יש צבעים שונים. צביעה כזו של הגרף נקראת צביעת קודקודים.
[עריכה] היסטוריה
בעבר היה מקובל לחשוב שמשפט ארבעת הצבעים היה ידוע לקרטוגרפים, אך נראה שלטענה זו אין בסיס. ככל הידוע לנו היום, הטענה עלתה בדעתו של פרנסיס גאטרי (Francis Guthrie) בשנת 1850, בעת שעסק בצביעת מפה של אנגליה. לאחר שניסה למצוא הוכחה במשך זמן מה, הוא סיפר על הבעיה לאחיו פרדריק, שלמד אצל המתמטיקאי אוגוסטוס דה-מורגן. דה-מורגן ניסה בלא הצלחה לעניין בנושא מתמטיקאים אחרים, עד שב- 1878 הובאה הבעיה לתשומת ליבו של ארתור קיילי, שהציג אותה בפני החברה המלכותית הבריטית.
'הוכחה' ראשונה להשערת ארבעת הצבעים פורסמה לראשונה בשנת 1879, על-ידי אלפרד קמפ (Kempe). קמפ הציע שיטה המבוססת על שרשראות של מדינות סמוכות, שאמורה הייתה בעקרון לאפשר הוספה של מדינה אחר מדינה למפה הצבועה, בלי להזדקק לצבע חמישי. ההוכחה נבדקה, והתקבלה על-דעת בני זמנו. ואולם, אחת-עשרה שנים מאוחר יותר הראה פרסי ג'ון היווד (Heawood) שהוכחה זו אינה נכונה. בנוסף, היווד הצליח להראות שחמישה צבעים מספיקים לצביעת כל מפה.
[עריכה] הכללות
משפט ארבעת הצבעים עוסק, כאמור, בצביעה של מפות על פני המישור. קל לראות שמשימה זו שקולה לצביעה של מפה כדורית, שגם עבורה מספיקים ארבעה צבעים. עם זאת, טופולוגים עסקו גם בשאלה כמה צבעים נחוצים למפה המצוירת על-פני משטחים אחרים, כגון טורוס או בקבוק קליין. את המשטחים הרלוונטיים (שהם משטחים חלקים קומפקטיים) אפשר למיין לפי שתי תכונות: מספר הצדדים של המשטח (אחד, כמו במקרה של בקבוק קליין, או שניים, כמו לכדור ולטורוס) ומאפיין אוילר 
, שאותו אפשר לחשב ממספר ה'חורים' במשטח (לכדור ולבקבוק קליין אין חורים, לטורוס יש אחד).
במאמרו מ- 1890 הראה היווד שבכל משטח למעט הכדור, מספר הצבעים הדרוש אינו עולה על ![[\frac{7+\sqrt{49-24\chi}}{2}]](../../../math/7/c/4/7c498b94b1ff38ef47ad5854e145c4f4.png)
. בפרט, הטורוס ובקבוק קליין (בשניהם 
) דורשים שבעה צבעים לכל היותר. ב- 1934 הראה פיליפ פרנקלין שעל-פני בקבוק קליין מספיקים ששה צבעים, וב- 1959 הראה Ringel שבכל מקרה אחר החסם של היווד הוא מדויק.
[עריכה] הוכחת משפט ארבעת הצבעים
בשנת 1976 נעזרו וולפגאנג האקן וקנת אפל מאוניברסיטת אילינוי בשרשראות של קמפ, כדי להראות שכל מפה אפשרית שקולה לאחת מבין 1,936 מפות שונות. לאחר מכן הם הריצו מחשב במשך 1,200 שעות כדי להראות שכל אחת ממפות אלה ניתנת לצביעה בארבעה צבעים. בשנת 1996 ניתנה הוכחה דומה, שבה היה די בבדיקה של 663 מפות. גם בדיקה זו דרשה הסתייעות במחשב.
[עריכה] לקריאה נוספת
- קנת' אפל וולפגאנג הייגן The Solution of the Four-Color-Map Problem, Scientific American, גליון 237, מס. 4, עמ' 108-121 (1977)
- Invitation to Combinatorial Topology, קיי פאן ומוריס , 1946, מלווה בהערות מאת הווארד איבס, 1967.
- סיימון סינג, המשפט האחרון של פרמה, הוצאת ידיעות אחרונות, 2000. עמ' 356-370.
