עדכון אחרון: 16 אוקטובר 2002 שעה 22:00 | שלח לי מכתב | צפה בספר האורחים | חתום בספר האורחים | אודות חדר המידע | דף ראשי

 

 

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

 

halemo

 

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

 

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

 

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

 

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

 

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

 

ההוכחה הושגה באמצעות מחשב.

 

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