Witam
Mam problem ze zrozumieniem dowodu twierdzenia Eulera ( 1736 ), które głosi że:
Graf spójny \(\displaystyle{ G=(V,E)}\) ma cykl Eulera \(\displaystyle{ \Leftrightarrow \forall _{v \in V} 2 | deg(v)}\)
Rozumiem dowód w prawo, ale mam problemy z implikacją w lewo. Konkretnie nie rozumiem, co tu jest założeniem indukcyjnym.
Dla \(\displaystyle{ m=3}\) twierdzenie oczywiście zachodzi. Dla \(\displaystyle{ m>3}\) wiemy z odpowiedniego lematu, że graf zawiera jakiś cykl C. Jeżeli cykl zawiera cały graf, to dowód się kończy. Jeżeli nie to usuwamy go, dzieląc graf na spójne składowe.
I właśnie tutaj jest problem. Wszędzie jest napisane, że z założenia indukcyjnego wiemy iż każdy graf o ilości krawędzi \(\displaystyle{ n < m}\) ma cykl Eulera. Dlaczego? Jakie tu jest założenie i teza indukcyjna?
Pozdrawiam,
Fray
Indukcja matematyczna w twierdzeniu Eulera 1736
-
- Użytkownik
- Posty: 73
- Rejestracja: 10 gru 2012, o 12:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 11 razy
Indukcja matematyczna w twierdzeniu Eulera 1736
Indukcja jest po liczbie krawędzi w grafie. Jeżeli są 3 krawędzie, to twierdzenie jest prawdziwe. Zakładamy więc, że dla każdego grafu, który ma mniej niż \(\displaystyle{ m}\) krawędzi implikacja zachodzi. Wykorzystujemy to założenie, rozbijając graf o \(\displaystyle{ m}\) krawędziach na takie, które spełniają założenie indukcyjne