Teoria grafów
Punkty i łączące je linie – tylko tyle trzeba, by powstał graf. A jednak ten sam obrazek opisuje mapę drogową, sieć znajomych, cząsteczkę i internet, a pytania, które można o niego zadać, od liczby potrzebnych kolorów po to, czy da się go narysować jednym pociągnięciem, zajmują matematyków od 1736 roku.
Wierzchołki i krawędzie
Graf ma wierzchołki, nazywane też węzłami, oraz krawędzie, z których każda łączy dwa wierzchołki. Nie ma znaczenia, gdzie wierzchołki są narysowane, liczy się tylko, które pary są połączone, więc ten sam graf może na papierze wyglądać zupełnie inaczej. Grafy w laboratorium są proste: żadna krawędź nie łączy wierzchołka z nim samym, a między dwoma wierzchołkami jest najwyżej jedna krawędź. Przy n wierzchołkach może być najwyżej n(n − 1) / 2 krawędzi; graf, który ma je wszystkie, nazywa się pełnym, a K5 to graf pełny o pięciu wierzchołkach.
Stopnie i lemat o uściskach dłoni
Stopień wierzchołka to liczba wychodzących z niego krawędzi. Dodaj wszystkie stopnie, a otrzymasz dokładnie dwa razy więcej, niż jest krawędzi, bo każda krawędź ma dwa końce i jest liczona raz przy każdym z nich. To lemat o uściskach dłoni: w każdej grupie uściski dłoni policzone osoba po osobie dają razem dwukrotność liczby uścisków. Wynika z niego też, że liczba wierzchołków o nieparzystym stopniu jest zawsze parzysta. Graf, w którym każdy wierzchołek ma ten sam stopień k, nazywa się k-regularnym.
Grafy spójne, drzewa i cykle
Graf jest spójny, gdy z każdego wierzchołka można dojść po krawędziach do każdego innego; w przeciwnym razie rozpada się na części, zwane składowymi spójności. Cykl to obchód, który wraca do punktu wyjścia, nie przechodząc dwa razy przez żaden wierzchołek, a długość najkrótszego cyklu to talia grafu. Spójny graf bez cykli to drzewo, a drzewo o n wierzchołkach ma zawsze dokładnie n − 1 krawędzi: o jedną mniej i się rozpada, o jedną więcej i pojawia się cykl. Każdy graf spójny zawiera drzewo rozpinające, czyli drzewo, które dociera do każdego wierzchołka, używając tylko części krawędzi.
Grafy dwudzielne i kolorowanie
Pokoloruj wierzchołki tak, aby żadna krawędź nie łączyła dwóch wierzchołków tego samego koloru. Najmniejsza liczba kolorów, która na to pozwala, to liczba chromatyczna. Jeden kolor wystarcza tylko wtedy, gdy nie ma krawędzi. Dwa kolory wystarczają dokładnie wtedy, gdy graf jest dwudzielny: jego wierzchołki dzielą się na dwie strony, a każda krawędź biegnie między nimi. Dénes Kőnig wykazał w 1936 roku, że jest to równoważne brakowi cykli o nieparzystej długości, bo w nieparzystym cyklu nie da się stosować dwóch kolorów na przemian. Dla trzech i więcej kolorów nie jest znany żaden równie prosty test: rozstrzygnięcie, czy wystarczą trzy kolory, jest problemem NP-zupełnym, więc programy przeszukują możliwości, tak jak robi to laboratorium.
Przykład: graf Petersena
Weź pięciokąt A–B–C–D–E i pięcioramienną gwiazdę F–H–J–G–I w jego wnętrzu, a następnie połącz każdy wierzchołek pięciokąta z jednym ramieniem gwiazdy: A–F, B–G, C–H, D–I i E–J. To graf Petersena, z 10 wierzchołkami i 15 krawędziami. Każdy wierzchołek ma stopień 3, więc suma stopni wynosi 30, czyli dwa razy 15. Najkrótszy cykl ma długość 5, więc graf nie ma trójkątów, ale pięciokąt jest cyklem nieparzystym, więc graf nie jest dwudzielny i potrzebuje 3 kolorów. Dowolne dwa wierzchołki dzielą najwyżej 2 krawędzie, więc jego średnica wynosi 2. Wszystkie dziesięć stopni jest nieparzystych, więc graf nie ma drogi Eulera, i nie da się go narysować bez przecięć.
Drogi Eulera i mosty Królewca
Królewiec (Königsberg) miał siedem mostów łączących cztery części lądu i ludzie zastanawiali się, czy da się przejść przez każdy most dokładnie raz. W 1736 roku Leonhard Euler wykazał, że nie, i tak narodziła się teoria grafów. Za każdym razem, gdy spacer przechodzi przez jakąś część lądu, wykorzystuje dwa mosty, więc tylko początek i koniec mogą mieć nieparzystą liczbę mostów, a wszystkie cztery części Królewca miały ich nieparzyście wiele. Drogę, która przechodzi każdą krawędź raz, nazywa się dziś drogą Eulera, a jeśli kończy się tam, gdzie się zaczęła – cyklem Eulera. Carl Hierholzer udowodnił w 1873 roku, że ten warunek jest też wystarczający: jeśli wszystkie krawędzie tworzą jedną całość, a najwyżej dwa stopnie są nieparzyste, droga istnieje, a jego metoda łączenia zamkniętych obchodów wciąż pozwala ją znaleźć.
Odległość, średnica i dopełnienie
Odległość między dwoma wierzchołkami to najmniejsza liczba krawędzi na ścieżce między nimi, a średnica to największa odległość w grafie; w grafie niespójnym jest nieskończona. Sieci społecznościowe mają małe średnice – na tym opiera się idea sześciu stopni oddalenia. Dopełnienie grafu ma te same wierzchołki i łączy dokładnie te pary, które nie były połączone. Spośród grafu i jego dopełnienia co najmniej jeden jest zawsze spójny.
Wypróbuj
Laboratorium otwiera się z grafem Petersena pokolorowanym trzema kolorami. Kliknij Stopnie i sprawdź lemat o uściskach dłoni, kliknij Dwudzielny, aby zobaczyć cykl nieparzysty, a potem wczytaj sześcian i zobacz, jak pojawiają się dwie strony. Wczytaj domek i kliknij Droga Eulera, aby zobaczyć, gdzie trzeba zacząć rysowanie jednym pociągnięciem. Narysuj własny graf i dodawaj krawędzie po jednej: obserwuj, jak najkrótszy cykl się skraca, średnica maleje, a liczba chromatyczna rośnie, gdy dochodzi ostatnia krawędź K4.
Często zadawane pytania
Czym różnią się marszruta, droga i ścieżka?
Marszruta to dowolny ciąg wierzchołków połączonych krawędziami, w którym mogą się powtarzać zarówno wierzchołki, jak i krawędzie. W drodze mogą się powtarzać wierzchołki, ale nie krawędzie, dlatego droga Eulera może przechodzić przez wierzchołek kilka razy. W ścieżce nie powtarza się ani jedno, ani drugie.
Czym jest twierdzenie o czterech barwach?
Mówi, że każdy graf, który można narysować na papierze bez przecinających się krawędzi, da się pokolorować co najwyżej czterema kolorami, więc żadna mapa nie potrzebuje więcej niż czterech. Udowodnili je w 1976 roku Kenneth Appel i Wolfgang Haken z pomocą komputera – było to pierwsze ważne twierdzenie udowodnione w ten sposób.
Czym jest cykl Hamiltona?
To cykl, który odwiedza dokładnie raz każdy wierzchołek, a nie każdą krawędź. Przypomina to pytanie Eulera, ale nie jest znany żaden prosty test: rozstrzygnięcie, czy graf ma taki cykl, jest problemem NP-zupełnym. Graf Petersena ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
Gdzie wykorzystuje się teorię grafów?
Planery tras przeszukują grafy dróg, wyszukiwarki szeregują strony internetowe według linków, kompilatory kolorują grafy, aby przydzielać rejestry procesora, plany zajęć unikają kolizji dzięki kolorowaniu grafu konfliktów, chemicy liczą cząsteczki jako grafy, a sieci komputerów, linii energetycznych i znajomych bada się jako grafy.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz laboratorium teorii grafów