משפט ארבעת הצבעים

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

מפה (גרף) הדורשת לפחות ארבעה צבעים

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

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

מפות וגרפים

מפה עם הגרף הדואלי

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

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