משפט ארבעת הצבעים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט החלפות: \1ניסיו\2\3 |
הוספת קישורים פנימיים והעברת סימוכין (קישור חיצוני) להערות השוליים. |
||
שורה 1:
'''משפט ארבעת הצבעים''' הוא תוצאה בולטת בהיסטוריה של [[טופולוגיה קומבינטורית|הטופולוגיה הקומבינטורית]] ושל [[תורת הגרפים]]. לפי המשפט, אפשר לצבוע כל [[מפה מדינית|מפת שטחים רציפים]], באופן שכל שתי מדינות בעלות [[קו גבול]] משותף נצבעות בצבע שונה, תוך שימוש בארבעה צבעים בלבד. מתמטיקאים החלו לחקור את הבעיה באמצע [[המאה ה-19]]. היא נודעה כ'השערת ארבעת הצבעים', וזכתה ל'הוכחות' שגויות רבות.
[[תמונה:Fourcolorsmap.png|שמאל|ממוזער|120px|מפה ([[גרף (תורת הגרפים)|גרף]]) הדורשת לפחות ארבעה
בניסוח מודרני, המשפט מבטיח שלכל [[גרף מישורי]] קיימת [[צביעת קודקודים]] בארבעה צבעים. אנשי תורת הגרפים מכירים הוכחות קלות יחסית לכך שקיימת צביעה ב'''חמישה''' צבעים, אבל ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב-[[1976]], והיא כרוכה בחיפוש ממוחשב על-פני אלפי מקרים. זו הייתה ההשערה המפורסמת הראשונה שהוכחה בעזרת מחשב, ובתחילה לא הייתה הסכמה כללית על תקפות ה[[הוכחה]], בעיקר בנימוק שלא הוכחה נכונותן של [[תוכנית מחשב|תוכניות המחשב]] עצמן. מאז נעשו ניסיונות רבים למצוא הוכחה סטנדרטית יותר, שיכולה לעמוד ל[[ביקורת עמיתים]] ללא עזרת מחשב. הוכחה כזו עדיין לא נמצאה.
שורה 21:
=== השקילות לצביעת קשתות של גרפים מדרגה 3 ===
במסגרת ניסיונו להוכיח את המשפט, הפיזיקאי הבריטי פיטר טייט
== הכללות ==
שורה 27:
משפט ארבעת הצבעים עוסק, כאמור, בצביעה של מפות על פני המישור. קל לראות שמשימה זו שקולה לצביעה של מפה כדורית, שגם עבורה מספיקים ארבעה צבעים. עם זאת, טופולוגים עסקו גם בשאלה כמה צבעים נחוצים למפה המצוירת על-פני משטחים אחרים, כגון [[טורוס]] או [[בקבוק קליין]]. את המשטחים הרלוונטיים (שהם [[יריעה חלקה|משטחים חלקים]] [[קומפקטיות|קומפקטיים]]) אפשר למיין לפי שתי תכונות: מספר הצדדים של המשטח (אחד, כמו במקרה של בקבוק קליין, או שניים, כמו לכדור ולטורוס) ו[[מאפיין אוילר]] <math>\ \chi</math>, שאותו אפשר לחשב ממספר ה'חורים' במשטח (לכדור ולבקבוק קליין אין חורים, לטורוס יש אחד).
במאמרו מ-[[1890]] הראה היווד שבכל משטח למעט הכדור, מספר הצבעים הדרוש אינו עולה על <math>(7+\sqrt{49-24\chi})/2</math>. בפרט, הטורוס ובקבוק קליין (בשניהם <math>\ \chi = 0</math>) דורשים שבעה צבעים לכל היותר. ב-[[1934]] הראה פיליפ פרנקלין שעל-פני בקבוק קליין מספיקים ששה צבעים, וב-[[1959]] הראה רינגל שבכל מקרה אחר החסם של היווד הוא מדויק.
== הוכחת משפט ארבעת הצבעים ==
בשנת [[1976]] נעזרו [[וולפגאנג האקן]] ו[[קנת אפל]] מ[[אוניברסיטת אילינוי באורבנה-שמפיין]] בשרשראות של קמפ, כדי להראות שכל מפה אפשרית שקולה לאחת מבין 1,936 מפות שונות. לאחר מכן הם הריצו תוכנית [[מחשב]] במשך 1,200 שעות כדי להראות שכל אחת ממפות אלה ניתנת לצביעה בארבעה צבעים. בשנת [[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.
| |||