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