משפט ארבעת הצבעים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 9:
[[תמונה:Four Colour Planar Graph.svg|שמאל|ממוזער|240px|מפה עם הגרף הדואלי]]
הקשר בין מפות מישוריות לבין [[גרף מישורי|גרפים מישוריים]] מבוסס על בניית ה[[גרף דואלי|גרף הדואלי]], שהיא בנייה סטנדרטית ב[[תורת הגרפים]]. בגרף המתאים למפה נתונה, כל מדינה מיוצגת על ידי קודקוד, וכל שתי מדינות שלהן יש גבול משותף מחוברות בקשת בין שני הקודקודים המתאימים. משמאל מוצגת דוגמה למפה ולגרף המתאים לה. הערה: ההתאמה מניחה כי שטח כל מדינה הוא רצוף, מה של תמיד מתקיים (לדוגמה אזור [[קלינינגרד]] ב[[רוסיה]]).
כעת, צביעת המדינות על המפה שקולה לבחירת צבע לכל קודקוד, באופן כזה שלשני קודקודים המחוברים בקשת יש צבעים שונים. צביעה כזו של הגרף נקראת [[צביעת קודקודים]].
| |||