Twierdzenie Ore

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Faner
Użytkownik
Użytkownik
Posty: 151
Rejestracja: 21 paź 2012, o 17:33
Płeć: Mężczyzna
Lokalizacja: katowice
Podziękował: 27 razy

Twierdzenie Ore

Post autor: Faner »

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.
Awatar użytkownika
Spektralny
Użytkownik
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

Twierdzenie Ore

Post autor: Spektralny »

Którego miejsca dowodu nie rozumiesz?

Faner
Użytkownik
Użytkownik
Posty: 151
Rejestracja: 21 paź 2012, o 17:33
Płeć: Mężczyzna
Lokalizacja: katowice
Podziękował: 27 razy

Twierdzenie Ore

Post autor: Faner »

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
ODPOWIEDZ