פורטל:מדעי המחשב/הידעת?/14

צביעה הדורשת לפחות ארבעה צבעים

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

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