-
Regularny
-
Pełny
Laboratorium teorii grafów
Graf to zbiór punktów, zwanych wierzchołkami, połączonych liniami, zwanymi krawędziami. Narysuj go tutaj kilkoma kliknięciami, a laboratorium powie ci, jaki to graf: z ilu części się składa, czy jest drzewem, ilu kolorów co najmniej potrzebuje, czy da się go narysować jednym pociągnięciem i wiele więcej. Kliknij własność, aby zobaczyć ją na swoim grafie, zmień krawędź i obserwuj, jak zmieniają się odpowiedzi. Kliknij puste miejsce, aby dodać wierzchołek. Kliknij wierzchołek, a potem drugi, aby połączyć je krawędzią; zrób to ponownie, aby usunąć krawędź. Przeciągnij wierzchołek, aby go przesunąć. Przełącz kliknięcie na Wymazuje i kliknij wierzchołek lub krawędź, aby je usunąć. Gdy wierzchołek jest zaznaczony, Delete go usuwa, a Esc odznacza. Kliknij własność, aby pokazać ją na grafie. Przykład wczytuje znany graf, Losowy graf tworzy nowy, Uporządkuj rozsuwa wierzchołki, a Dopełnienie łączy dokładnie te pary, które nie były połączone. Ctrl+Z cofa jeden krok.
Jak to działa
- Kliknij puste miejsce, aby dodać wierzchołek. Kliknij wierzchołek, a potem drugi, aby je połączyć; zrób to ponownie, aby usunąć krawędź. Przeciągnij wierzchołek, aby go przesunąć.
- Odczytaj własności pod grafem i kliknij jedną z nich, aby ją pokazać: kolorowanie, dwie strony, drogę Eulera, drzewo rozpinające, najkrótszy cykl lub średnicę.
- Wczytaj przykładowy graf, choćby graf Petersena, utwórz losowy graf, weź dopełnienie albo przełącz kliknięcie na Wymazuje, aby usuwać wierzchołki i krawędzie.
Co oznaczają własności
Stopień wierzchołka to liczba wychodzących z niego krawędzi. Graf jest spójny, gdy z każdego wierzchołka można dojść po krawędziach do każdego innego, a jest drzewem, gdy jest spójny i nie ma cyklu. Jest dwudzielny, gdy jego wierzchołki dzielą się na dwie strony, a każda krawędź biegnie między nimi, co zachodzi dokładnie wtedy, gdy nie ma cyklu o nieparzystej długości. Liczba chromatyczna to najmniejsza liczba kolorów, przy której sąsiednie wierzchołki mają różne kolory. Długość najkrótszego cyklu nazywa się talią grafu, a średnica to największa odległość między dwoma wierzchołkami, liczona w krawędziach.
Rysowanie jednym pociągnięciem
Droga Eulera przechodzi każdą krawędź dokładnie raz. Leonhard Euler zauważył w 1736 roku, rozważając siedem mostów Królewca (Königsberg), co stoi na przeszkodzie: za każdym razem, gdy droga przechodzi przez wierzchołek, zużywa dwie jego krawędzie. Zatem albo wszystkie stopnie są parzyste i droga może skończyć się tam, gdzie się zaczęła, albo dokładnie dwa stopnie są nieparzyste i droga musi prowadzić od jednego z tych wierzchołków do drugiego. Carl Hierholzer udowodnił później, że jeśli wszystkie krawędzie tworzą jedną całość, ten warunek również wystarcza. Wczytaj przykład z domkiem i znajdź miejsce, w którym trzeba zacząć rysowanie.
Często zadawane pytania
Czym jest graf w teorii grafów?
Zbiorem punktów, zwanych wierzchołkami lub węzłami, oraz linii łączących niektóre ich pary, zwanych krawędziami. To nie wykres funkcji: graf opisuje tylko, co jest połączone z czym. Mapy drogowe, sieci społecznościowe, cząsteczki i sieci komputerowe to wszystko grafy.
Jak wyznaczana jest liczba chromatyczna?
Laboratorium próbuje pokolorować graf jednym kolorem, potem dwoma, potem trzema i tak dalej, a dla każdej liczby przeszukuje wszystkie istotne możliwości, kolorując zawsze jako następny ten wierzchołek, którego sąsiedzi używają już najwięcej kolorów. Pierwsza liczba, która się sprawdza, to liczba chromatyczna. Dla grafów, które można tu narysować, trwa to najwyżej chwilę; przy bardzo trudnym grafie przeszukiwanie kończy się wcześniej, a wynik jest pokazywany jako górne ograniczenie.
Kiedy graf ma drogę Eulera?
Gdy wszystkie jego krawędzie tworzą jedną całość i najwyżej dwa wierzchołki mają nieparzysty stopień. Bez wierzchołków nieparzystego stopnia istnieje cykl Eulera, który kończy się tam, gdzie się zaczyna; przy dwóch każda droga Eulera zaczyna się w jednym z nich i kończy w drugim. Liczba wierzchołków nieparzystego stopnia jest zawsze parzysta, więc nigdy nie wynosi dokładnie jeden.
Czym jest dopełnienie grafu?
To graf na tych samych wierzchołkach, którego krawędziami są dokładnie te pary, które wcześniej nie były połączone. Dopełnienie dopełnienia to graf wyjściowy. Na przykład dopełnienie grafu Petersena jest 6-regularne, bo każdy wierzchołek był połączony z 3 spośród 9 pozostałych.
Dlaczego graf Petersena jest tak słynny?
To mały graf z 10 wierzchołkami i 15 krawędziami, który obala wiele obiecujących hipotez. Każdy wierzchołek ma stopień 3, najkrótszy cykl ma długość 5, dowolne dwa wierzchołki dzielą najwyżej 2 krawędzie i nie da się go narysować bez przecinających się krawędzi. Laboratorium otwiera się właśnie z nim.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora