Jednym pociągnięciem
Wierzchołki nieparzyste
Narysowane krawędzie
Sposoby narysowania

    • 0 wierzchołków nieparzystych: cykl, z dowolnego wierzchołka z powrotem do niego
    • 2 wierzchołki nieparzyste: ścieżka z jednego do drugiego
    • 4 lub więcej: niemożliwe jednym pociągnięciem

    Metoda

    Więcej o ścieżkach i cyklach Eulera

    Wyszukiwarka ścieżek Eulera

    Czy da się narysować domek świętego Mikołaja bez odrywania ołówka i bez powtarzania linii? Da się, ale tylko zaczynając w jednym z dwóch dolnych rogów, a z każdego z nich jest 44 sposobów. Powodem jest stopień wierzchołka, czyli liczba linii, które się w nim schodzą: za każdym razem, gdy ołówek przez niego przechodzi, zużywa dwie z nich. Leonhard Euler odkrył tę regułę w 1736 roku przy siedmiu mostach królewieckich. Obrysuj figurę samodzielnie, zobacz, gdzie utkniesz i dlaczego, poproś o podpowiedź albo popatrz, jak rysuje ją algorytm. Wybierz figurę i obrysuj ją: dotknij wierzchołka, aby zacząć, a potem po kolei krawędzi lub kolejnych wierzchołków, albo przeciągaj od wierzchołka do wierzchołka. Każdej krawędzi można użyć tylko raz. Cofnij cofa jeden krok, Podpowiedź pokazuje następną bezpieczną krawędź, a Rozwiąż odtwarza krok po kroku algorytm Fleury'ego lub Hierholzera. Wierzchołki nieparzyste są wypełnione, a znaczek przy każdym wierzchołku to jego stopień. W trybie Rysuj dotknięcie pustego miejsca dodaje wierzchołek, a dotknięcie dwóch wierzchołków łączy je, kolejne dodaje drugą krawędź; przeciągnij wierzchołek, aby go przesunąć. Wymaż usuwa wierzchołki i krawędzie. Gdy nieparzystych wierzchołków jest więcej niż dwa, Dodaj wstawia krawędzie, dzięki którym figurę da się narysować.

    Jak to działa

    1. Wybierz figurę, na przykład siedem mostów królewieckich, domek świętego Mikołaja albo gwiazdę, albo narysuj własną w trybie Rysuj, z dowolną liczbą krawędzi między dwoma wierzchołkami.
    2. Dotknij wierzchołka, aby zacząć, a potem po kolei krawędzi lub wierzchołków, albo przeciągaj od wierzchołka do wierzchołka. Gdy utkniesz, wiersz stanu wyjaśni dlaczego; Cofnij cofa krok, a Podpowiedź pokazuje bezpieczną krawędź.
    3. Przeczytaj regułę stopni pod figurą, dodaj do figury niemożliwej proponowane krawędzie albo naciśnij Rozwiąż, aby zobaczyć, jak algorytm Fleury'ego lub Hierholzera rysuje ją krok po kroku.

    Dlaczego decydują wierzchołki nieparzyste

    Pociągnięcie przechodzące przez wierzchołek wchodzi jedną linią, a wychodzi drugą, więc zużywa linie tego wierzchołka parami. Tylko tam, gdzie pociągnięcie się zaczyna lub kończy, linia może zostać bez pary. Dlatego wierzchołek o nieparzystej liczbie linii musi być początkiem albo końcem. Bez wierzchołków nieparzystych pociągnięcie kończy się tam, gdzie się zaczęło: to cykl Eulera. Przy dwóch biegnie od jednego do drugiego: to ścieżka Eulera. Przy czterech lub więcej końców jest za dużo jak na jedno pociągnięcie, a k wierzchołków nieparzystych wymaga k/2 pociągnięć. Królewiec miał cztery części lądu z pięcioma, trzema, trzema i trzema mostami: wszystkie cztery nieparzyste, więc żaden spacer nie mógł przejść przez każdy most raz. Jeden nowy most między dwiema z nich umożliwiłby spacer.

    Algorytmy Fleury'ego i Hierholzera

    Wiedzieć, że figurę da się narysować, to nie to samo co ją narysować: nieostrożne pociągnięcie może odciąć się od linii, których jeszcze potrzebuje. Algorytm Fleury'ego z 1883 roku zapobiega temu jedną regułą: nigdy nie przechodź przez most, czyli linię, której usunięcie podzieliłoby pozostałe linie na dwie części, chyba że innej linii nie ma. Algorytm Hierholzera, z pracy wydanej w 1873 roku, jest szybszy: idź gdziekolwiek, aż utkniesz, co może zdarzyć się tylko na starcie, a potem z wierzchołka trasy, który ma jeszcze wolne linie, przejdź kolejną zamkniętą pętlę i wstaw ją do trasy. Jego czas rośnie proporcjonalnie do liczby krawędzi i to w ten sposób komputery znajdują ścieżki Eulera.

    Często zadawane pytania

    Jaka jest różnica między ścieżką Eulera a cyklem Eulera?

    Oba używają każdej krawędzi grafu dokładnie raz. Cykl Eulera kończy się tam, gdzie się zaczął; ścieżka Eulera kończy się gdzie indziej. Graf spójny ma cykl, gdy każdy wierzchołek ma stopień parzysty, a ścieżkę, gdy dokładnie dwa wierzchołki mają stopień nieparzysty; ścieżka biegnie wtedy od jednego do drugiego.

    Dlaczego nie da się przejść przez każdy z siedmiu mostów królewieckich dokładnie raz?

    Narysuj każdą część lądu jako wierzchołek, a każdy most jako krawędź. Wyspa Kneiphof miała pięć mostów, a pozostałe trzy części po trzy, więc wszystkie cztery wierzchołki są nieparzyste. Spacer może zaczynać się lub kończyć tylko w wierzchołku nieparzystym, a cztery to za dużo. Dodanie jednego mostu między dwoma z nich zostawia dwa wierzchołki nieparzyste i spacer staje się możliwy.

    Na ile sposobów można narysować domek świętego Mikołaja?

    Na 44 z każdego z dwóch dolnych rogów, razem na 88, jeśli inną kolejność lub inny kierunek liczyć jako inny sposób. Z żadnego innego wierzchołka się nie da, bo dolne rogi to jedyne dwa o nieparzystej liczbie linii. Aplikacja liczy w ten sposób sposoby dla małych figur.

    Czym jest most w grafie?

    Krawędzią, której usunięcie dzieli graf spójny na dwie części. Algorytm Fleury'ego nigdy nie przechodzi przez most wśród pozostałych krawędzi, dopóki ma inny wybór, bo zostawiłby za sobą część figury. W tej aplikacji pociągnięcie, które utknęło po zbyt wczesnym przejściu przez most, dowiaduje się, który to był krok.

    Czy między dwoma wierzchołkami może być więcej niż jedna krawędź?

    Tak. Graf z krawędziami równoległymi nazywa się multigrafem, a Królewiec go wymaga: dwa mosty łączyły Kneiphof z każdym brzegiem. W trybie Rysuj dotknij ponownie dwóch wierzchołków, aby dodać między nimi kolejną krawędź, aż do czterech. Reguła stopni działa tak samo i liczy każdą krawędź.

    Chcesz wypróbować?

    Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

    Przejdź do edytora