יישומים של תורת הגרפים
גרפים מישוריים
גרף G אמור להיות מישורי אם ניתן לייצג אותו על מישור בצורה כזו שהקודקודים הם כל נקודות נקודתיות, הקצוות הם עקומות פשוטות, ושני קצוות אינם פוגשים זה את זה מלבד במסופי שלהם. לדוגמה, K 4, הגרף השלם בארבע קודקודים, הוא מישורי, כפי שמראה איור 4A.
אומרים ששני גרפים הם הומורפיים אם ניתן להשיג את שניהם מאותו גרף על ידי חלוקות משנה של קצוות. לדוגמה, הגרפים באיור 4 א ואיור 4 ב הם הומורפיים.
תרשים K m, n הוא גרף שעבורו ניתן לחלק את מערך הקודקוד לשתי קבוצות משנה, האחת עם קודקודים m והשנייה עם קודקודים n. כל שני קודקודים של אותה תת-קבוצה אינם סמוכים זה לזה, ואילו שני קודקודים של קבוצות משנה שונות צמודים זה לזה. המתמטיקאי הפולני קזימייז 'קוראטובסקי בשנת 1930 הוכיח את המשפט המפורסם הבא:
תנאי הכרחי ומספיק כדי שגרף G יהיה מישורי הוא שהוא אינו מכיל תת-גרף הומומורפי של K 5 או K 3,3 המוצג באיור 5.
כיווץ אלמנטרי של גרף G הוא טרנספורמציה של G לתרשים G 1 חדש, כך ששני הקודקודים הסמוכים u ו- υ של G מוחלפים על ידי קודקוד w חדש ב- G 1 ו- w הוא צמוד ב- G 1 לכל הקודקודים ל אשר U או υ סמוכים ב- G. גרף G * אמר כי הוא התכווצות של G אם ניתן להשיג G * מ- G על ידי רצף של התכווצויות אלמנטריות. להלן אפיון נוסף של גרף מישורי בזכות המתמטיקאי הגרמני ק 'וגנר בשנת 1937.
גרף הוא מישורי אם ורק אם הוא אינו מתכווץ ל- K 5 או K 3,3.
בעיית המפה עם ארבעה צבעים
במשך יותר ממאה שנים פיתרון בעיית המפות בעלת ארבע הצבעים חמק מכל אנליסט שניסה זאת. ייתכן שהבעיה משכה את תשומת לבו של מוביוס, אך נראה שההתייחסות הראשונה שנכתבה אליו היא מכתב של פרנסיס גוטרי אחד לאחיו, תלמידו של אוגוסטוס דה מורגן, בשנת 1852.
הבעיה נוגעת למפות מישוריות - כלומר חלוקות משנה של המטוס לאזורים שאינם חופפים ומגבילים בעקומות סגורות ופשוטות. במפות גיאוגרפיות נצפתה אמפירית, בכמה שיותר מקרים מיוחדים שניסו, כי לכל היותר יש צורך בארבעה צבעים על מנת לצבוע את האזורים כך ששני אזורים שחולקים גבול משותף תמיד צובעים אחרת, וב מקרים מסוימים שלפחות ארבעה צבעים נחוצים. (אזורים שנפגשים רק בנקודה מסוימת, כמו מדינות קולורדו ואריזונה בארצות הברית, אינם נחשבים כגבול משותף). פורמליזציה של התבוננות אמפירית זו מהווה את מה שמכונה "משפט ארבעת הצבעים". הבעיה היא להוכיח או להפריך את הקביעה שזה המצב בכל מפה מישורית. ניתן להוכיח בקלות כי שלושה צבעים לא יספיקו, בעוד שהספקתם של חמישה צבעים הוכחה בשנת 1890 על ידי המתמטיקאי הבריטי PJ Heawood.
בשנת 1879 הציע א.ב. קמפ, אנגלי, פיתרון לבעיית ארבעת הצבעים. אף כי הווד הראה כי טענתו של קמפה הייתה פגומה, שניים ממושגיו הוכיחו פורה בחקירה מאוחרת יותר. אחד מאלה, הנקרא בלתי נמנע, מציין נכונה את חוסר האפשרות לבנות מפה בה נעדרת כל אחת מארבע תצורות (תצורות אלה מורכבות מאזור עם שני שכנים, אחד עם שלוש, אחד עם ארבע ואחד עם חמש). הרעיון השני, זה של צמצום, לוקח את שמו מההוכחה התקפה של קמפה שאם יש מפה הדורשת לפחות חמישה צבעים וכוללת אזור עם ארבעה (או שלושה או שניים) שכנים, חייבת להיות מפה הדורשת חמישה צבעים צבעים למספר קטן יותר של אזורים. הניסיון של קמפה להוכיח את צמצום המפה המכילה אזור עם חמישה שכנים היה שגוי, אך הוא תוקן בהוכחה שפורסמה בשנת 1976 על ידי קנת אפל וולפגנג האקן מארצות הברית. ההוכחה שלהם עוררה ביקורת מסוימת מכיוון שהיא חייבה את הערכתם של 1,936 מקרים שונים, שכל אחד מהם כלל עד 500,000 פעולות לוגיות. אפל, הייקן ומשתפי הפעולה שלהם תיכננו תוכניות שאיפשרו למחשב דיגיטלי גדול לטפל בפרטים אלה. על מנת לבצע את המשימה נדרש המחשב יותר מ -1,000 שעות, וההוכחה הרשמית המתקבלת היא באורך של כמה מאות עמודים.
מחזורי אוילריאן ובעיית גשר קוניגסברג
G multigraph מורכב מסט V (G) של קודקודים לא ריק, ותת קבוצה E (G) של קבוצת הזוגות הלא מסודרים של אלמנטים ברורים של V (G) עם תדר f ≥ 1 המחובר לכל זוג. אם הזוג (x 1, x 2) עם תדר f שייך ל- E (G), אז קודקודים x 1 ו- x 2 מצטרפים לקצוות f.
מחזור אוילריאני של G מולטיגרף הוא שרשרת סגורה בה כל קצה מופיע בדיוק פעם אחת. אוילר הראה שמולטיגרף הוא בעל מחזור אוילריאני אם ורק אם הוא מחובר (מלבד נקודות מבודדות) ומספר הקודקודים בדרגה מוזרה הוא אפס או שניים.
בעיה זו עלתה תחילה באופן הבא. נהר הפרגל, שנוצר במפגש בין שני סניפיו, עובר בעיירה קניגסברג ונחל משני צדי האי קניפהוף. היו שבעה גשרים, כפי שמוצג באיור 6 א. תושבי העיירה תהו האם ניתן לצאת לטיול ולחצות כל גשר פעם אחת בלבד. זה שווה למציאת מחזור אוילריאני למולטיגרף באיור 6 ב. אוילר הראה שזה בלתי אפשרי מכיוון שיש ארבעה קודקודים של סדר מוזר.
