גרף מישורי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Legobot (שיחה | תרומות)
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q547823
שורה 76:
 
== גרפים מישוריים ומפות ==
 
כש[[קרטוגרפיה|קרטוגרף]] מצייר [[מפה מדינית]], הוא משתדל לצבוע מדינות שכנות ב[[צבע]]ים שונים, כדי להקל על ההבחנה ביניהן. הדרך הטבעית לחקור מצבים כאלה בתורת הגרפים היא להגדיר את [[גרף דואלי|הגרף הדואלי]] למפה, שבו הצמתים הם המדינות, וזוג צמתים מחוברים בקשת רק כאשר המדינות המתאימות שכנות זו לזו. מכיוון שהמפה המקורית היא מישורית (או כדורית, אם מדובר במפה כלל-עולמית), הגרף המתקבל הוא גרף מישורי.
 
המשימה של הגאוגרף היא [[צביעה (תורת הגרפים)|לצבוע]] את צומתיצמתי הגרף, באופן שזוג צמתים מחוברים ייצבעו בצבעים שונים. [[משפט ארבעת הצבעים]] מבטיח שתמיד ניתן לעשות זאת בארבעה צבעים או פחות. בלשון אחרת, המשפט מבטיח שלכל גרף מישורי יש 4-[[צביעה (תורת הגרפים)|צביעה]].
 
==קישורים חיצוניים==