Twierdzenie Ore
-
- Użytkownik
- Posty: 151
- Rejestracja: 21 paź 2012, o 17:33
- Płeć: Mężczyzna
- Lokalizacja: katowice
- Podziękował: 27 razy
Twierdzenie Ore
Czy bylby ktos w stanie udowodnic Twierdzenie Ore i przedstawic mi tutaj dowod ? Tylko prosze nie kopiowac linkow z google itp. Przeszukalem juz te strony i niestety nie rozumie tego dowodu, dlatego prosilbym aby w bardzo zrozumialy sposob ktos go przedstawil.
- Spektralny
- Użytkownik
- Posty: 3976
- Rejestracja: 17 cze 2011, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Praga, Katowice, Kraków
- Podziękował: 9 razy
- Pomógł: 929 razy
-
- Użytkownik
- Posty: 151
- Rejestracja: 21 paź 2012, o 17:33
- Płeć: Mężczyzna
- Lokalizacja: katowice
- Podziękował: 27 razy
Twierdzenie Ore
Moze pokaze na przykladzie :
Wiem ze dowodzimy nie wprost. Bierzemy sobie graf niehamiltonowski, czyli taki ktory nie posiada cyklu hamiltona majacy n wierzcholkow. Dodajac nowe krawedzie doprowadzimy do tego ze graf jest prawie hamiltonowski, czyli ze dodanie jednej krawedzi spowoduje ze powstanie cyklu hamiltona. ( Skad wiadomo ze to w ogole mozliwe i dlaczego mozna ot tak dodac krawedzie ? )
I stad niby wynika ze powstaje droga v1 - > v2 ->v3 .. -> vn , ale graf nie jest hamiltonowski wiec v1 i vn nie sa sasiadami skad niby wynika ze deg(v1) + deg(v2 >= n ( z czego to wynika ? ) Musi zatem istniec wierzcholek vi sasiadzujacy z v1 oraz vi-1 sasiadujacy z vn i otrzymujemy cykl hamiltona
Dowod jest troche inny niz tez z wikipedi, powstawialem w nawiasach momenty ktorych nie rozumie
Wiem ze dowodzimy nie wprost. Bierzemy sobie graf niehamiltonowski, czyli taki ktory nie posiada cyklu hamiltona majacy n wierzcholkow. Dodajac nowe krawedzie doprowadzimy do tego ze graf jest prawie hamiltonowski, czyli ze dodanie jednej krawedzi spowoduje ze powstanie cyklu hamiltona. ( Skad wiadomo ze to w ogole mozliwe i dlaczego mozna ot tak dodac krawedzie ? )
I stad niby wynika ze powstaje droga v1 - > v2 ->v3 .. -> vn , ale graf nie jest hamiltonowski wiec v1 i vn nie sa sasiadami skad niby wynika ze deg(v1) + deg(v2 >= n ( z czego to wynika ? ) Musi zatem istniec wierzcholek vi sasiadzujacy z v1 oraz vi-1 sasiadujacy z vn i otrzymujemy cykl hamiltona
Dowod jest troche inny niz tez z wikipedi, powstawialem w nawiasach momenty ktorych nie rozumie