לא פעם בעיות מתמטיות צצות מתוך סיטואציות יומיומיות של אנשי מקצוע. כך היה גם בסוגיה שבה נעסוק הפעם – בעיית ארבעת הצבעים. מקור הבעיה הוא באנגליה של המאה ה-19. בשנת 1852 הבחין המתמטיקאי פרנסיס גָאתרִי שאם רוצים לצבוע את מפת מחוזות אנגליה, כך שכל שני מחוזות שכנים יהיו בצבעים שונים, מספיקים ארבעה צבעים. גאתרי שאל אם זה נכון רק למפת אנגליה או שאפשר לצבוע כל מפה בארבעה צבעים (או פחות), כך שלא יהיו שני אזורים בעלי גבול משותף שצבעם זהה.
מימין: מפת מחוזות אנגליה ללא צביעה; משמאל: המפה בארבעה צבעים | תרשים: Marnanel, ויקיפדיה
התשובה היא שאכן אפשר לצבוע כל מפה בארבעה צבעים, והבעיה מוכרת עתה כ"משפט ארבעת הצבעים". בדומה לבעיות רבות אחרות במתמטיקה, כמו "משפט פרמה", גם כאן הדרך לפתרון הייתה ארוכה ועברו 124 שנים עד שנמצאה ההוכחה. לפני שנפרט יותר על המשפט ועל השלבים להוכחתו נשאל מה העניין בשאלה הזו?
אפשר לצבוע ללא קושי כל מפה כך שכל שני אזורים סמוכים בה יהיו בצבע שונה: אם יש $n$ אזורים, אפשר להשתמש ב-$n$ צבעים שונים והבעיה נפתרת. אבל זו לא חוכמה – אנחנו רוצים פתרון "יעיל" יותר שיעזור גם במקרה שיש מגבלה על מספר הצבעים שבהם אנו יכולים לצבוע את המפה.
מתברר שלמפות רבות מספיקים שלושה צבעים בלבד, אך יש מפות שדורשות צבע רביעי. זה קורה כשיש אזור שמוקף במספר אי-זוגי של אזורים שנוגעים זה בזה במעגל, כמו שמופיע בציור הבא (שעליו מבוסס סמל הדפדפן גוגל כרום). הסיבה היא שבמקרה של מפה כזו עם ארבעה אזורים, אם צובעים את האזור שבמרכז בצבע אחד אז אף אחד מהאזורים הנוגעים בו לא יכולים להיות בצבע שלו. בנוסף אליו, כל אזור נוגע בעוד שני אזורים, ולכן חייבים להיות ארבעה צבעים לפחות. במפה עם מספר זוגי של אזורים חיצוניים, לעומת זאת, אפשר לצבוע אזורים הנמצאים זה מול זה באותו צבע (ראו בציור).
מפה שדורשת ארבעה צבעים לפחות | תרשים: דוד שי, ויקיפדיה
דוגמה למפה עם אזור מרכזי שמוקף במספר זוגי של אזורים הנוגעים זה בזה
אזורים כאלה, המוקפים בשלושה אזורים הנוגעים זה בזה, אכן קיימים במפת מחוזות אנגליה וגם במפות אחרות, ולכן יש מקרים שדורשים ארבעה צבעים לפחות, אם כי הם אינם נפוצים. אחד הצעדים הראשונים בדרך להוכחה היתה טענה שהוכיח המתמטיקאי אוגוסט דה-מורגן שלפיה אי אפשר למצוא מפה דומה שתכלול חמישה אזורים כך שכל אחד מהם גובל בכל השאר. אך זה לא מספק לנו הוכחה למשפט.
שלבים בהוכחת המשפט
הראשון שסיפק הוכחה, או לפחות חשב שהצליח, היה עורך הדין ארתור קמפ בשנת 1879. קמפ פישט את הבעיה: אם לאזור יש שלושה שכנים, אפשר לכווץ אותו עד שייעלם וכך תתקבל מפה פשוטה יותר (ראו למטה). את המפה הפשוטה יותר צובעים בשלושה צבעים ואז מחזירים את האזור שכווץ וצובעים אותו בצבע שונה משלושת שכניו. קמפ המשיך וקבע סדרת כללים לצביעה, שמטפלים גם באזורים שיש להם ארבעה או חמישה שכנים, תוך שהוא מכווץ את האזורים ומחזיר אותם.
מימין: מפה ובה אזור עם שלושה שכנים; משמאל: מפה פשוטה יותר עם אזור "מכווץ"
ההוכחה נראתה אלגנטית ויפה, אבל 11 שנים לאחר שהוצעה היא הופרכה. עם זאת, המתמטיקאים השתמשו בשיטה של קמפ כדי להוכיח שאפשר להסתפק בחמישה צבעים לכל מפה. כאן הם נתקלו בפער מסוים – הם הוכיחו שחמישה צבעים מספיקים, אבל לא הצליחו למצוא מפה שזקוקה ליותר מארבעה צבעים. עם זאת, לא עלה בידם לתת הוכחה מתמטית שאכן מספיקים רק ארבעה צבעים.
במשך השנים היו ניסיונות נוספים למצוא הוכחה. הם אמנם לא פתרו את הבעיה עצמה, אך סיפקו פתרונות לבעיות פשוטות יותר (לדוגמה, שכל מפה שיש בה 26 אזורים אפשר לצבוע בארבעה צבעים בלבד) או שתרמו רעיונות שסייעו בהמשך להוכחה. רעיון אחד כזה, שנקרא "התצורה הניתנת לצמצום", נתן המתמטיקאי האמריקאי פיליפ פרנקלין. הוא הראה שההוכחה של קמפ נכונה במפות שבהן לאזורים יש שלושה או ארבעה שכנים, אך לא לאזורים שיש להם חמישה שכנים.
פרנקלין אמנם לא הוכיח את המשפט, אך נתן אסטרטגיה להוכחה שנשענת גם היא על עקרון של פישוט המפה וצביעה של המפה הפשוטה יותר. הבעיה היא שההוכחה שלו דרשה חישובים רבים וממושכים כדי למצוא את כל הקבוצות האפשריות של אזורים שכנים במפה. רק בשנת 1976, בעבודה משותפת של וולפגנג האקן וקנת אפל ובעזרת מחשב, המשימה הושלמה. השניים המציאו שיטות לצמצם את מספר הבדיקות הנדרשות ולהאיץ אותן, ותהליך הבדיקה נמשך בסופו של דבר בערך אלף שעות. במחשבים של ימינו, אגב, התהליך נמשך כשעה בלבד!
עוד הערה קטנה נדרשת: המשפט נכון בתנאים מסוימים שאינם תואמים תמיד למציאות. המשפט דורש שאזור יהיה, במונחים מתמטיים, קשיר או רציף. כלומר, האזור אינו מופרד לתת-אזורים לא סמוכים. בפועל יש מדינות שמחולקות לכמה אזורים נפרדים, ולפי כללי צביעת המפות כל האזורים של מדינה צריכים להיצבע באותו צבע. התנאי זה יוצר אילוץ שסותר את משפט ארבעת הצבעים, ולכן מפות כאלה דורשות חמישה צבעים.
הבעיה ותורת הגרפים
בעיית ארבעת הצבעים, והדרכים ששימשו להוכחת הפתרון שלה, נראית אולי שונה מבעיות מתמטיות רבות, שנפתרות בכלים אלגבריים או גיאומטריים. סיבה אפשרית לכך היא שהבעיה שייכת לענף שנקרא "תורת הגרפים", שהוא ענף מודרני יחסית של המתמטיקה שהעיסוק בו התחיל רק במאה ה-18. ראשון העוסקים בה הוא המתמטיקאי הידוע והפורה לאונרדו אוילר, שפתר את החידה המפורסמת של "בעיית הגשרים של קניגסברג". המאמר שלו משנת 1736 שבו תיאר את הפתרון נחשב למאמר הראשון בתורת הגרפים.
"תורת הגרפים", כמשתמע משמה, עוסקת בתכונות של גרפים שמייצגים מבנים מופשטים. הגדרה כללית ופשוטה לגרף היא אוסף של נקודות שמכונות צמתים או קודקודים ומסומנות באות $\mathsf{V}$ (Vertices), המחוברים בקשתות המסומנות באות $\mathsf{E}$ (Edges). מתקיים כי כל קשת היא זוג קודקודים שביניהם היא מקשרת. השימוש בגרפים נפוץ בתחומים רבים, כגון מידול של רשת כבישים, מידול של רשתות חברתיות או למידה על מולקולות בכימיה ובפיסיקה. גם משחק הסודוקו המוכר מהעיתונים היומיים הוא למעשה בעיה בתורת הגרפים!
דוגמאות לגרפים
אפשר להבדיל בין גרפים לפי תכונות שלהם. דוגמה אחת היא ההבחנה בין גרף מישורי לגרף לא מישורי: גרף מישורי הוא גרף שאפשר לצייר במישור בלי שהקשתות יחתכו זו את זו חוץ מאשר בקודקודים.
שני גרפים מישוריים (מימין) לעומת שני גרפים לא מישוריים (משמאל)
נחזור לבעיית ארבעת הצבעים. את הבעיה אפשר לנסח במושגים מתמטיים של תורת הגרפים: האם לכל גרף מישורי קיימת צביעת קודקודים בארבעה צבעים?
כלומר בעיית ארבעת המישורים מתייחסת לגרף $n$-צביע, שהוא גרף שאפשר לצבוע את הקודקודים שלו ב-$n$ צבעים כך ששני קודקודים סמוכים לא יהיו באותו צבע. מספר הצביעה הוא המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים. את בעיית ארבעת הצבעים אפשר לתרגם לשפה של תורת הגרפים, כך שכל מדינה או אזור במפה יהיו שקולים לקודקוד בגרף. הגרף המתקבל צריך להיות 4-צביע. בתמונה אפשר לראות ציור של גרף כזה. לא נראה את זה כאן, אך כשהבעיה מנוסחת כבעיית צביעה בתורת הגרפים היא רלוונטית גם לבעיות יומיומיות אחרות, כגון תכנון לוחות זמנים.
תרגום בעיית ארבעת הצבעים לבעיה בתורת הגרפים
יפה לראות איך נושא שבא מתחום הקרטוגרפיה (תורת היצירה, העריכה, הקריאה, העיבוד וההדפסה של מפות גיאוגרפיות) יוצר בעיה שהעסיקה במשך השנים מתמטיקאים מתחומים רבים, כמו תורת הגרפים, טופולוגיה וקומבינטוריקה, ושנפתרה בסופו של דבר בשילוב של מתמטיקה עם מדעי המחשב. הבעיה אמנם נפתרה, אך עדיין נותרו שאלות פתוחות לגביה – למשל האם אפשר לצמצם עוד יותר את מספר האזורים לבדיקה כך שלא יהיה צורך במחשב לצורך כך. בעיני מתמטיקאים רבים הוכחה חישובית אינה הוכחה מספקת והם רוצים למצוא הוכחה פשוטה יותר ו"מתמטית" יותר. אבל עדיין מדובר בהישג מרשים בבעיה שנותרה במשך שנים רבות בלתי פתורה.
יעל נוריק
המחלקה להוראת המדעים
מכון ויצמן למדע
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בתגובה לכתבה זו ואנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
