Εφαρμογές της θεωρίας γραφημάτων
Επίπεδα γραφήματα
Ένα γράφημα G λέγεται ότι είναι επίπεδο εάν μπορεί να αναπαρασταθεί σε επίπεδο με τέτοιο τρόπο ώστε οι κορυφές να είναι όλα ξεχωριστά σημεία, οι άκρες να είναι απλές καμπύλες και να μην συναντώνται δύο ακμές μεταξύ τους εκτός από τους ακροδέκτες τους. Για παράδειγμα, το K 4, το πλήρες γράφημα σε τέσσερις κορυφές, είναι επίπεδο, όπως δείχνει το Σχήμα 4Α.
Δύο γραφήματα λέγεται ότι είναι ομοιόμορφα εάν και τα δύο μπορούν να ληφθούν από το ίδιο γράφημα με υποδιαιρέσεις των άκρων. Για παράδειγμα, τα γραφήματα στο Σχήμα 4Α και στο Σχήμα 4Β είναι ομοιόμορφα.
Το γράφημα K m, n είναι ένα γράφημα για το οποίο το σύνολο κορυφών μπορεί να χωριστεί σε δύο υποσύνολα, το ένα με κορυφές m και το άλλο με n κορυφές. Οποιαδήποτε δύο κορυφές του ίδιου υποσυνόλου δεν γειτνιάζουν, ενώ οι δύο κορυφές διαφορετικών υποομάδων είναι παρακείμενες. Ο Πολωνός μαθηματικός Kazimierz Kuratowski το 1930 απέδειξε το ακόλουθο διάσημο θεώρημα:
Μια αναγκαία και ικανή συνθήκη για ένα γράφημα G να είναι επίπεδη είναι ότι δεν περιέχει ένα υπογράφημα homeomorphic είτε να Κ 5 ή Κ 3,3 παρουσιάζεται στο Σχήμα 5.
Μια στοιχειώδης συστολή ενός γραφήματος G είναι ένας μετασχηματισμός του G σε ένα νέο γράφημα G 1, έτσι ώστε δύο γειτονικές κορυφές u και υ του G να αντικατασταθούν από μια νέα κορυφή w στο G 1 και το w να είναι δίπλα στο G 1 σε όλες τις κορυφές σε το οποίο είτε u ή υ είναι δίπλα στο G. Ένα γράφημα G * λέγεται ότι είναι μια συστολή του G εάν το G * μπορεί να ληφθεί από το G με μια ακολουθία στοιχειωδών συστολών. Το παρακάτω είναι ένας άλλος χαρακτηρισμός ενός επίπεδου γραφήματος λόγω του Γερμανού μαθηματικού K. Wagner το 1937.
Ένα γράφημα είναι επίπεδο εάν και μόνο εάν δεν είναι συμβατό με το K 5 ή το K 3,3.
Το τετράχρωμο πρόβλημα του χάρτη
Για περισσότερο από έναν αιώνα, η λύση του τετραχρωμικού προβλήματος του χάρτη έφυγε από κάθε αναλυτή που το προσπάθησε. Το πρόβλημα μπορεί να έχει προσελκύσει την προσοχή του Μόμπους, αλλά η πρώτη γραπτή αναφορά σε αυτό φαίνεται να είναι μια επιστολή ενός Francis Guthrie στον αδελφό του, μαθητή του Augustus De Morgan, το 1852.
Το πρόβλημα αφορά τους επίπεδες χάρτες - δηλαδή, υποδιαιρέσεις του επιπέδου σε μη επικαλυπτόμενες περιοχές που οριοθετούνται από απλές κλειστές καμπύλες. Σε γεωγραφικούς χάρτες έχει παρατηρηθεί εμπειρικά, σε όσες ειδικές περιπτώσεις έχουν δοκιμαστεί, ότι, το πολύ, απαιτούνται τέσσερα χρώματα για να χρωματιστούν οι περιοχές έτσι ώστε δύο περιοχές που μοιράζονται ένα κοινό όριο να έχουν πάντα διαφορετικό χρώμα και ορισμένες περιπτώσεις που απαιτούνται τουλάχιστον τέσσερα χρώματα. (Περιφέρειες που συναντώνται μόνο σε ένα σημείο, όπως οι πολιτείες του Κολοράντο και της Αριζόνα στις Ηνωμένες Πολιτείες, δεν θεωρείται ότι έχουν κοινό όριο). Η τυποποίηση αυτής της εμπειρικής παρατήρησης αποτελεί αυτό που ονομάζεται «τετράχρωμο θεώρημα». Το πρόβλημα είναι να αποδείξουμε ή να διαψεύσουμε τον ισχυρισμό ότι αυτό ισχύει για κάθε επίπεδο χάρτη. Αυτά τα τρία χρώματα δεν αρκούν αποδεικνύεται εύκολα, ενώ η επάρκεια πέντε χρωμάτων αποδείχθηκε το 1890 από τον Βρετανό μαθηματικό PJ Heawood.
Το 1879, ο AB Kempe, ένας Άγγλος, πρότεινε μια λύση του τετραχρωμικού προβλήματος. Αν και ο Heawood έδειξε ότι το επιχείρημα του Kempe ήταν λανθασμένο, δύο από τις έννοιες του αποδείχθηκαν καρποφόρα σε μεταγενέστερη έρευνα. Ένα από αυτά, που ονομάζεται αναπόφευκτη, δηλώνει σωστά την αδυναμία κατασκευής ενός χάρτη στον οποίο απουσιάζει κάθε μία από τις τέσσερις διαμορφώσεις (αυτές οι διαμορφώσεις αποτελούνται από μια περιοχή με δύο γείτονες, μία με τρεις, μία με τέσσερις και μία με πέντε). Η δεύτερη έννοια, αυτή της μειωσιμότητας, παίρνει το όνομά της από την έγκυρη απόδειξη του Kempe ότι εάν υπάρχει ένας χάρτης που απαιτεί τουλάχιστον πέντε χρώματα και περιέχει μια περιοχή με τέσσερις (ή τρεις ή δύο) γείτονες, τότε πρέπει να υπάρχει ένας χάρτης που απαιτεί πέντε χρώματα για μικρότερο αριθμό περιοχών. Η προσπάθεια του Kempe να αποδείξει την αναγωγιμότητα ενός χάρτη που περιέχει μια περιοχή με πέντε γείτονες ήταν εσφαλμένη, αλλά διορθώθηκε σε μια απόδειξη που δημοσιεύθηκε το 1976 από τους Kenneth Appel και Wolfgang Haken των Ηνωμένων Πολιτειών. Η απόδειξή τους προσέλκυσε κάποια κριτική επειδή απαιτούσε την αξιολόγηση 1.936 ξεχωριστών περιπτώσεων, καθεμία από τις οποίες αφορούσε έως και 500.000 λογικές πράξεις. Οι Appel, Haken και οι συνεργάτες τους επινόησαν προγράμματα που επέτρεψαν σε έναν μεγάλο ψηφιακό υπολογιστή να χειριστεί αυτές τις λεπτομέρειες. Ο υπολογιστής απαιτούσε περισσότερες από 1.000 ώρες για την εκτέλεση της εργασίας και η προκύπτουσα επίσημη απόδειξη έχει μήκος αρκετών εκατοντάδων σελίδων.
Οι κύκλοι του Eulerian και το πρόβλημα της γέφυρας Königsberg
Ένα πολλαπλό γράμμα G αποτελείται από ένα άδειο σύνολο V (G) κορυφών και ένα υποσύνολο E (G) του συνόλου μη τακτοποιημένων ζευγών διακριτών στοιχείων του V (G) με συχνότητα f ≥ 1 συνδεδεμένη σε κάθε ζεύγος. Εάν το ζεύγος (x 1, x 2) με τη συχνότητα f ανήκει στο E (G), τότε οι κορυφές x 1 και x 2 ενώνονται με τα άκρα f.
Ένας κύκλος Eulerian ενός πολυγραφικού G είναι μια κλειστή αλυσίδα στην οποία κάθε άκρο εμφανίζεται ακριβώς μία φορά. Ο Euler έδειξε ότι ένα multigraph διαθέτει έναν κύκλο Euler εάν και μόνο εάν είναι συνδεδεμένο (εκτός από μεμονωμένα σημεία) και ο αριθμός των κορυφών του περίεργου βαθμού είναι είτε μηδέν είτε δύο.
Αυτό το πρόβλημα προέκυψε αρχικά με τον ακόλουθο τρόπο. Ο ποταμός Pregel, που σχηματίζεται από τη συμβολή των δύο κλαδιών του, διασχίζει την πόλη Königsberg και ρέει και στις δύο πλευρές του νησιού Kneiphof. Υπήρχαν επτά γέφυρες, όπως φαίνεται στο Σχήμα 6Α. Οι κάτοικοι αναρωτήθηκαν αν ήταν δυνατόν να περπατήσουμε και να διασχίσουμε κάθε γέφυρα μία και μόνο φορά. Αυτό ισοδυναμεί με την εύρεση ενός κύκλου Euler για το πολύγραμμα στο Σχήμα 6Β. Ο Euler το έδειξε αδύνατο επειδή υπάρχουν τέσσερις κορυφές περίεργης τάξης.
