Witam. Proszę o pomoc w rozwiązaniu zadania. Tutaj jest zdjęcie zadania. .
Chodzi o ciąg Eulera.
Trzeba wybrać pkt początkowy i przejechać po wszystkich liniach, a na koniec wrócić do pkt początkowego. Uwaga(Linie nie mogą się powtórzyć, nie można przejechać 2 rady po tej samej Linii).
Proszę o pomoc.
Pozdrawiam.
Algorytm Fleury’ego. Droga/ciąg Eulera
-
Straznik Teksasu
- Użytkownik
- Posty: 426
- Rejestracja: 29 paź 2015, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 21 razy
- Pomógł: 90 razy
Algorytm Fleury’ego. Droga/ciąg Eulera
Nie da rady czegoś takiego zrobić, masz przynajmniej 2 węzły z którego odchodzą po 3 gałęzie. Jak wpłyniesz do takiego węzła przez jakąś gałąź to wypłyniesz z niej drugą gałęzią. Zostaje jeszcze tylko jedna gałąź przez którą musisz wpłynąć, ale nie dasz rady wtedy wypłynąć z węzła, a tym samym wrócić do puntu początkowego (który powinien znajdować się w drugim węźle z 3 gałęziami).
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Graf_eulerowski-
Waylays
- Użytkownik
- Posty: 59
- Rejestracja: 26 lis 2014, o 19:14
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 19 razy
- Pomógł: 8 razy
Algorytm Fleury’ego. Droga/ciąg Eulera
Ten konkretny graf nie ma ani drogi Eulera, ani cyklu Eulera i wynika to z prostego w dowodzie twierdzenia (właściwie to twierdzeń). Twój graf ma po prostu za dużo wierzchołków stopnia nieparzystego.
Tw. Graf spójny, który ma cykl Eulera, ma wszystkie wierzchołki parzyste.
Dw.
W cyklu Eulera wybieramy dowolny wierzchołek i wychodzącą z niego krawędź, którą usuwamy. Następnie usuwamy kolejne krawędzie. Przechodząc przez każdy wierzchołek zmniejszamy jego stopień o \(\displaystyle{ 2}\). Po usunięciu wszystkich krawędzi otrzymamy zbiór wierzchołków stopnia \(\displaystyle{ 0}\). Zatem Pierwotnie stopień każdego wierzchołka był parzysty.
Tw. Graf spójny, który ma drogę Eulera, ma wszystkie wierzchołki stopnia parzystego, za wyjątkiem co najwyżej \(\displaystyle{ 2}\).
Dw.
Jeżeli droga Eulera z \(\displaystyle{ U}\) do \(\displaystyle{ V}\) jest niezamknięta, to dołączając krawędź \(\displaystyle{ (U,V)}\) zwiększamy stopnie \(\displaystyle{ U}\) i \(\displaystyle{ V}\) o \(\displaystyle{ 1}\) i zamykamy cykl Eulera. Zatem stopnie pozostałych wierzchołków muszą być parzyste.
Tw. Graf spójny, który ma cykl Eulera, ma wszystkie wierzchołki parzyste.
Dw.
W cyklu Eulera wybieramy dowolny wierzchołek i wychodzącą z niego krawędź, którą usuwamy. Następnie usuwamy kolejne krawędzie. Przechodząc przez każdy wierzchołek zmniejszamy jego stopień o \(\displaystyle{ 2}\). Po usunięciu wszystkich krawędzi otrzymamy zbiór wierzchołków stopnia \(\displaystyle{ 0}\). Zatem Pierwotnie stopień każdego wierzchołka był parzysty.
Tw. Graf spójny, który ma drogę Eulera, ma wszystkie wierzchołki stopnia parzystego, za wyjątkiem co najwyżej \(\displaystyle{ 2}\).
Dw.
Jeżeli droga Eulera z \(\displaystyle{ U}\) do \(\displaystyle{ V}\) jest niezamknięta, to dołączając krawędź \(\displaystyle{ (U,V)}\) zwiększamy stopnie \(\displaystyle{ U}\) i \(\displaystyle{ V}\) o \(\displaystyle{ 1}\) i zamykamy cykl Eulera. Zatem stopnie pozostałych wierzchołków muszą być parzyste.