Witam.
Bardzo prosiłbym o nakierowanie jak należy rozwiązać poniższe zadanie.
Ucieczka z labiryntu. Dany jest dowolny spójny graf \(\displaystyle{ G}\). Pokaż że następująca metoda zapewnia przejście wszystkich jego krawędzi zaczynając od wierzchołka \(\displaystyle{ v}\):
1. nigdy nie przechodzimy tej samej krawędzi dwa razy w tym samym kierunku;
2. jeśli napotkamy wierzchołek \(\displaystyle{ x\ne v}\), w którym dotychczas nie byliśmy, to zaznaczamy krawędź którą do niego dotarliśmy;
3. używamy tej zaznaczonej krawędzi do opuszczenie \(\displaystyle{ x}\) dopiero gdy nie ma innej alternatywy.
Pokaż, że po przejściu całego \(\displaystyle{ G}\) wrócimy do wierzchołka \(\displaystyle{ v}\).
Nie próbowałem jeszcze robić tej pierwszej części, bo po przeczytaniu ostatniego zdania mam wrażenie, że albo w zadaniu jest błąd, albo ja nie zauważam jakiejś oczywistości. Wydaje mi się, że jeśli wiemy tylko tyle, że graf jest spójny, to przecież niekoniecznie po przejściu przez wszystkie krawędzie trafimy do tego pierwszego wierzchołka.
Z góry dziękuję za pomoc.
Grafy - ucieczka z labiryntu
-
- Użytkownik
- Posty: 1
- Rejestracja: 25 sty 2019, o 14:11
- Płeć: Mężczyzna
- Lokalizacja: Krk
Grafy - ucieczka z labiryntu
Ostatnio zmieniony 25 sty 2019, o 16:25 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.