Graf to zbiór wierzchołków i krawędzi, które je łączą. Oczywiście nie musi istnieć połączenie pomiędzy każdymi dwoma dowolnymi wierzchołkami. Przykłady grafów zamieściłem na ilustracji powyżej. Zwyczajowo zbiór wierzchołków oznaczamy przez V, a zbiór krawędzi przez E. Graf G oznaczamy krótko przez G=(V,E). W matematyce jest osobny dział, który zajmuje się teorią grafów, jednak nam - na potrzeby tego posta - nie jest potrzebne więcej wiadomości.
Co różni te trzy grafy? Otóż jednego z nich nie jesteśmy w stanie narysować bez odrywania ręki od kartki. Pamiętam, gdy siostra przechwalała się rysując kopertę (na rysunku: drugi graf) jednym pociągnięciem ołówka w czasie, gdy mi się to nie udawało. Co jest więc kluczem do tego, by dało narysować się taki graf i jak to zrobić?
Potrzebne nam będzie kilka definicji. Ścieżką nazywamy taki ciąg wierzchołków, że pomiędzy dwoma kolejnymi wyrazami ciągu istnieje krawędź je łącząca. Drogą zaś będziemy oznaczać ścieżkę, której wierzchołki są różne. Jeśli zaś weźmiemy drogę zamkniętą (czyli taką, której początkowy wyraz jest równy ostatniemu), to mamy cykl. Dodatkowo - cykl Eulera jest cyklem, który przechodzi przez każdą krawędź dokładnie jeden raz. Graf Eulera jest takim grafem, który posiada cykl Eulera. Który z tych grafów jest więc grafem Eulera?
Odpowiedź brzmi: drugi i trzeci. W przypadku środkowego grafu mówimy jedynie o grafie półeulerowskim, gdyż (w uproszczeniu) ważne jest to, z którego wierzchołka zaczniemy rysować cykl. I to właśnie jest kluczem do wcześniej wspomnianego triku mojej siostry. Są tylko dwa wierzchołki, z których możemy rozpocząć rysowanie grafu tak, by nie musieć później odrywać ręki. Mianowicie v1 i v5. Z tych wierzchołków wychodzi nieparzysta liczba krawędzi. Ważne jest również to, że istnieją dokładnie dwa takie wierzchołki, pozostałe zaś są parzystego stopnia. Z czym to jest związane?
Spójrzmy na rysunek powyżej - w sytuacji po lewej stronie mamy wierzchołek stopnia 3, a więc nieparzystego. W tej sytuacji jedyną możliwością by uzyskać cykl jest rozpoczęcie rysowania z tego wierzchołka, gdyż w przeciwnym przypadku (rysunek po prawej) uzyskamy parzystą liczbę stopni w wierzchołku (mamy widoczne wyjście i wejście). To świadczy o tym, że aby narysować graf bez odrywania ręki liczba wierzchołków musi być parzysta, bądź też - jak w grafie drugim - tylko dwa wierzchołki mogą być nieparzyste.
Ktoś by pomyślał - po co nam to wszystko? Matematyka zajmuje się wieloma dziedzinami, które jeszcze nie mają swoich zastosować, ale kto wie - może w jakiejś dziedzinie życia przydadzą nam się własności grafów eulerowskich. Dlatego właśnie trzeba rozwijać nawet te gałęzie matematyki, które jeszcze nie mają swoich zastosowań.
Brak komentarzy:
Prześlij komentarz