הצגת המקור של הדף "משפט ארבעת הצבעים"

'''משפט ארבעת הצבעים''' הוא תוצאה בולטת בהיסטוריה של [[טופולוגיה קומבינטורית|הטופולוגיה הקומבינטורית]] ושל [[תורת הגרפים]]. לפי המשפט, אפשר לצבוע כל [[מפה מדינית]], באופן שכל שתי מדינות בעלות [[קו גבול]] משותף נצבעות בצבע שונה, תוך שימוש בארבעה צבעים לכל היותר. מתמטיקאים החלו לחקור את הבעיה באמצע [[המאה ה-19]]. היא נודעה כ'השערת ארבעת הצבעים', וזכתה ל[[הוכחה שגויה|הוכחות שגויות]] רבות. 
[[קובץ:World map with four colours.svg|ממוזער|מפת העולם ב-4 צבעים]]
[[קובץ:Fourcolorsmap.png|שמאל|ממוזער|120px|מפה ([[גרף (תורת הגרפים)|גרף]]) הדורשת לפחות ארבעה [[צבע]]ים]]
בניסוח מודרני, המשפט מבטיח שלכל [[גרף מישורי]] קיימת [[צביעת קודקודים]] בארבעה צבעים. אנשי תורת הגרפים מכירים הוכחות קלות יחסית לכך שקיימת צביעה ב'''חמישה''' צבעים, אבל ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב-[[1976]], והיא כרוכה בחיפוש ממוחשב על-פני אלפי מקרים. זו הייתה ההשערה המפורסמת הראשונה ש[[הוכחה בעזרת מחשב]], ובתחילה לא הייתה הסכמה כללית על תקפות ה[[הוכחה]], בעיקר בנימוק שלא הוכחה נכונותן של [[תוכנית מחשב|תוכניות המחשב]] עצמן. מאז נעשו ניסיונות רבים למצוא הוכחה סטנדרטית יותר, שיכולה לעמוד ל[[ביקורת עמיתים]] ללא עזרת מחשב. הוכחה כזו עדיין לא נמצאה.

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

== מפות וגרפים ==

[[קובץ:Four Colour Planar Graph.svg|שמאל|ממוזער|240px|מפה עם הגרף הדואלי]]
הקשר בין מפות מישוריות לבין [[גרף מישורי|גרפים מישוריים]] מבוסס על בניית ה[[גרף דואלי|גרף הדואלי]], שהיא בנייה סטנדרטית ב[[תורת הגרפים]]. בגרף המתאים למפה נתונה, כל מדינה מיוצגת על ידי קודקוד, וכל שתי מדינות שלהן יש גבול משותף מחוברות בקשת בין שני הקודקודים המתאימים. משמאל מוצגת דוגמה למפה ולגרף המתאים לה. 

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

==היסטוריה==

בעבר היה מקובל לחשוב שמשפט ארבעת הצבעים היה ידוע ל[[קרטוגרפיה|קרטוגרפים]], אך נראה שלטענה זו אין בסיס. ככל הידוע לנו היום, הטענה עלתה בדעתו של פרנסיס גאת'רי (Francis Guthrie) בשנת [[1852]], בעת שעסק בצביעת מפה של מחוזות [[אנגליה]]. לאחר שניסה למצוא הוכחה במשך זמן מה, הוא סיפר על הבעיה לאחיו פרדריק, שלמד אצל המתמטיקאי [[אוגוסטוס דה-מורגן]]. דה-מורגן ניסה בלא הצלחה לעניין בנושא מתמטיקאים אחרים, עד שב-[[1878]] הובאה הבעיה לתשומת לבו של [[ארתור קיילי]], שהציג אותה בפני [[החברה המלכותית הבריטית]]. 

'הוכחה' ראשונה להשערת ארבעת הצבעים פורסמה לראשונה בשנת [[1879]], על ידי [[אלפרד קמפ]] (Kempe). קמפ הציע שיטה המבוססת על שרשראות של מדינות סמוכות, שאמורה הייתה לאפשר הוספה של מדינה אחר מדינה למפה הצבועה, מבלי להזדקק לצבע חמישי. ההוכחה נבדקה, והתקבלה על-דעת בני זמנו. ואולם, 11 שנה מאוחר יותר הראה [[פרסי ג'ון היווד]] (Heawood) שההוכחה אינה נכונה. בנוסף, היווד הראה שחמישה צבעים מספיקים לצביעת כל מפה.

=== השקילות לצביעת קשתות של גרפים מדרגה 3 ===

במסגרת ניסיונו להוכיח את המשפט, הפיזיקאי הבריטי {{קישור שפה|אנגלית|Peter Tait (physicist)|פיטר טייט}}{{הערה|[http://users.wpi.edu/~bservat/blanusa08.pdf Blanuˇsa Double]}} הוכיח שצביעת מפות בארבעה צבעים שקולה לטענה הבאה: לכל [[גרף רגולרי|גרף 3-רגולרי]] [[גרף מישורי|מישורי]] [[גרף קשיר|2-קשיר-קשתות]] (כלומר, כזה שנשאר קשיר גם לאחר מחיקת אחת הקשתות) יש [[צביעת קשתות]] (כלומר, התאמה של צבע לכל קשת באופן ששתי קשתות נפגשות מקבלות צבעים שונים) בשלושה צבעים.{{הערה|1=Louis H. Kauffman, [http://www.math.uic.edu/~kauffman/MapReform.pdf Reformulating the map color theorem], Discrete Mathematics, Volume 302, Issues 1-3, 28 October 2005, Pages 145-172, }}

== הכללות ==

משפט ארבעת הצבעים עוסק, כאמור, בצביעה של מפות על פני המישור. קל לראות שמשימה זו שקולה לצביעה של מפה כדורית, שגם עבורה מספיקים ארבעה צבעים. עם זאת, טופולוגיים עסקו גם בשאלה כמה צבעים נחוצים למפה המצוירת על-פני משטחים אחרים, כגון [[טורוס]] או [[בקבוק קליין]]. את המשטחים הרלוונטיים (שהם [[יריעה חלקה|משטחים חלקים]] [[קומפקטיות|קומפקטיים]]) אפשר למיין לפי שתי תכונות: מספר הצדדים של המשטח (אחד, כמו במקרה של בקבוק קליין, או שניים, כמו לכדור ולטורוס) ו[[מאפיין אוילר]] <math>\ \chi</math>, שאותו אפשר לחשב ממספר ה'חורים' במשטח (לכדור ולבקבוק קליין אין חורים, לטורוס יש אחד). 

במאמרו מ-[[1890]] הראה היווד שבכל משטח למעט הכדור, מספר הצבעים הדרוש אינו עולה על <math>\frac {7+\sqrt{49-24\chi}}{2}</math>. בפרט, הטורוס ובקבוק קליין (בשניהם <math>\ \chi = 0</math>) דורשים שבעה צבעים לכל היותר. ב-[[1934]] הראה {{קישור שפה|אנגלית|Philip Franklin|פיליפ פרנקלין}} שעל-פני בקבוק קליין מספיקים שישה צבעים, וב-[[1959]] הראה {{קישור שפה|אנגלית|Gerhard Ringel|גרהרד רינגל}} שבכל מקרה אחר החסם של היווד הוא מדויק.

== הוכחת משפט ארבעת הצבעים == 

בשנת [[1976]] נעזרו [[וולפגאנג האקן]] ו[[קנת אפל]] מ[[אוניברסיטת אילינוי באורבנה-שמפיין]] בשרשראות של קמפ, כדי להראות שקיימת משפחה סופית של מפות (בהוכחה המקורית - 1936 מפות), שאם אפשר לצבוע את כולן, אז אפשר לצבוע בארבעה צבעים כל מפה אפשרית. הבדיקה שאכן מדובר במשפחה כזו דרשה חישוב מפורט ועתיר הסתעפויות, שנמשך (במחשבים של אותה תקופה) כ-1200 שעות. בשנת [[1996]] ניתנה הוכחה בעלת אופי דומה על ידי ניל רוברטסון, דניאל פ. סנדרס, [[פול סימור (מתמטיקאי)|פול סימור]] ורובין תומאס שבה היה די בבדיקה של 633 מפות. גם בדיקה זו דרשה הסתייעות במחשב.{{הערה|[http://people.math.gatech.edu/~thomas/FC/fourcolor.html The Four Color Theorem],{{כ}} School of Mathematics,{{כ}} באתר Georgia Tech,{{כ}} 8 בנובמבר 2007}}
רוברטסון וחבריו אף מצאו אלגוריתם ריבועי (שזמן הריצה שלו פרופורציוני לריבוע מספר הקודקודים) לצביעת גרף מישורי בארבעה צבעים.{{הערה|N. Robertson, D. P. Sanders, P. D. Seymour & R. Thomas, Efficiently
four-coloring planar graphs, Proceedings of the ACM Symposium on the
Theory of Computing, 28 (1996), 571-575.}}

== ראו גם ==

* [[בעיית הדויגר-נלסון]]

==לקריאה נוספת==
* קנת' אפל וולפגאנג הייגן ''The Solution of the Four-Color-Map Problem'', Scientific American, גיליון 237, מס. 4, עמ' 108-121 (1977)
* ''Invitation to Combinatorial Topology'', קיי פאן ומוריס, 1946, מלווה בהערות מאת הווארד איבס, 1967.
* [[סיימון סינג]], '''[[המשפט האחרון של פרמה (ספר)|המשפט האחרון של פרמה]]''', הוצאת ידיעות אחרונות, 2000. עמ' 356–368.
* [[איאן סטיוארט (מתמטיקאי)|איאן סטיוארט]], '''תיבת האוצרות המתמטיים של פרופסור סטיוארט''', [[כנרת זמורה-ביתן דביר]], 2012, הפרק "משפט ארבעת הצבעים", עמ' 22–29.

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{לא מדויק|1=post_list/?s=משפט+ארבעת+הצבעים|2=משפט ארבעת הצבעים}}
* {{MathWorld}}
* [http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html סקירת בעיית ארבעת הצבעים ב-MacTutor] {{אנגלית}}
* {{אנציקלופדיה למתמטיקה|Four-colour_problem}}
* [http://www.math.gatech.edu/~thomas/FC/fourcolor.html הוכחה חדשה למשפט ארבעת הצבעים] {{אנגלית}}
* {{בריטניקה}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:בעיות נודעות במתמטיקה]]
[[קטגוריה:משפטים בתורת הגרפים|ארבעת הצבעים]]
[[קטגוריה:משפטים בטופולוגיה|ארבעת הצבעים]]
[[קטגוריה:הוכחה באמצעות מחשב]]