Czy da się narysować figurę bez odrywania ołówka i bez powtarzania żadnego odcinka? Często rozstrzyga nie kształt obrazka, lecz liczba połączeń w wybranych punktach. Zamienimy rysunek na graf: punkty będą wierzchołkami, a odcinki krawędziami.
Co liczy stopień wierzchołka
Stopień to liczba końców krawędzi dochodzących do wierzchołka. Zwykły odcinek wnosi jeden koniec do każdego z dwóch końców. Pętla zaczynająca się i kończąca w tym samym wierzchołku wnosi do niego dwa. Na początek pracuj z rysunkami bez pętli.
Jeśli linie przecinają się tylko wizualnie, musisz ustalić, czy w miejscu przecięcia wolno zmienić kierunek. Jeśli tak, dodajesz wierzchołek i dzielisz krawędzie. Jeśli nie, jest to skrzyżowanie bez połączenia. Zasada musi być jasna przed liczeniem.
Dlaczego pojawia się parzystość
W wierzchołku pośrednim każde wejście zużywa jedną krawędź, a wyjście drugą. Krawędzie łączą się w pary. Wyjątkiem mogą być początek i koniec przejścia. Dlatego przejście po wszystkich krawędziach bez powtórzeń może mieć najwyżej dwa wierzchołki nieparzystego stopnia.
Dla grafu, którego wszystkie wierzchołki o dodatnim stopniu są połączone ze sobą drogami, warunek jest również wystarczający: zero nieparzystych stopni pozwala wrócić do początku, a dwa pozwalają przejść od jednego z nich do drugiego. To kryterium dotyczy krawędzi, nie zakazu wielokrotnego odwiedzania punktu.
Domek z przekątnymi
Oznacz narożniki kwadratu kolejno A, B, C, D, zaczynając od lewego dolnego. E jest szczytem dachu. Narysuj AB, BC, CD, DA, AC, BD, DE i CE. Przecięcie przekątnych nie jest w tym modelu dodatkowym wierzchołkiem.
Stopnie A i B wynoszą po 3, C i D po 4, a E ma stopień 2. Są dokładnie dwa stopnie nieparzyste. Jedna poprawna trasa to A–B–C–A–D–C–E–D–B. Sprawdź osiem kolejnych krawędzi: każda pochodzi z listy i żadna się nie powtarza.
Kiedy wynik jest niemożliwy
Gwiazda z jednym środkiem i czterema oddzielnymi ramionami ma środek stopnia 4 oraz cztery końce stopnia 1. Cztery nieparzyste stopnie wykluczają rysunek jedną kreską na podanych zasadach. Nie musisz próbować wszystkich kolejności.
- Najpierw ustal wierzchołki i listę krawędzi.
- Sprawdź połączenie wszystkich części.
- Policz stopnie, a potem liczbę stopni nieparzystych.
- Przy dwóch nieparzystych zacznij w jednym z nich.
To zastosowanie rozumowania o parzystości. Jeśli potrzebujesz narysować model na siatce, pomocny będzie prosty geoplan, ale nie zakładaj, że pomiar długości odcinków rozstrzyga możliwość przejścia. Długość odcinka we współrzędnych i liczba połączeń opisują dwie inne własności rysunku.
Inny przykład strategii opartej na strukturze, a nie szczęśliwej próbie, to gra w 21 żetonów. Zamiast stopni wierzchołków śledzimy tam resztę liczby żetonów po kolejnych ruchach.