Matematyka dyskretna, zadanie nr 4774

Autor	Zadanie / Rozwiązanie
brightnesss postów: 113	2016-08-13 13:40:57 Witam, mam ogromną prośbę. Czy mógłby mi ktoś wytłumaczyć twierdzenie Eulera dla grafów tak od początku do końca. Wiem, że w internecie jest duzo dowodów, ale ich nie rozumiem :/

tumor postów: 8070	2016-08-15 19:16:12 Rozumiem, że chodzi o twierdzenie mówiące, że graf spójny jest eulerowski wtw każdy wierzchołek ma parzysty stopień. Zasadniczo dowody są proste, więc lepiej się wczytać w nie głębiej niż szukać jeszcze prostszych. Nie jesteśmy w przedszkolu. Lemat Jeśli w grafie każdy wierzchołek ma stopień co najmniej 2, to graf zawiera cykl. Dowód lematu Grafy z pętlą czy krawędzią wielokrotną spełniają tezę. Dla grafów prostych rozumujemy tak: graf ma skończoną liczbę wierzchołków. $v_0$ wybieramy dowolnie, następnie jeśli mamy wierzchołek $v_k$, to $v_{k+1}$ dobieramy tak, by był on różny od $v_k$ i połączony z $v_k$ krawędzią, której dotychczas nie wykorzystywaliśmy. Da się zawsze taki znaleźć, bo stopień zawsze jest co najmniej 2. Dostajemy ciąg wierzchołków $v_0,v_1,...$ w którym z uwagi na skończoność zbioru wierzchołków któryś wierzchołek musi się powtórzyć. W momencie powtórzenia otrzymujemy cykl. Twierdzenie Graf spójny jest eulerowski wtw stopnie wszystkich wierzchołków są parzyste. Dowód twierdzenia. Jeśli jest eulerowski, to oczywiście stopnie wierzchołków są parzyste. To jest takie strasznie na chłopski rozum. Jeśli jedziesz po Polsce, to każde miasto oznacza tyle samo wjazdów co wyjazdów z niego. Prawda? W drugą stronę dowód nie jest tak do bólu trywialny, choć pozostaje łatwy. Zastosujemy indukcję po liczbie wierzchołków n. Dla 1 czy 2 wierzchołków twierdzenie jest oczywiste. Przyjmijmy zatem, że dla n-1 mamy twierdzenie udowodnione i rozpatrzmy graf spójny o liczbie wierzchołków n. Na podstawie lematu zawiera on cykl $C_1$. Wykreślmy krawędzie należące do cyklu $C_1$. Otrzymamy graf, który niekoniecznie jest spójny. Powtarzamy w każdym maksymalnym spójnym podgrafie wyszukiwanie cyklu, a jeśli podgraf ma mniej wierzchołków niż n, to używamy cyklu Eulera. (Izolowane wierzchołki pomijamy). W efekcie otrzymujemy cykle (być może cykle Eulera), w których krawędzie się nie powtarzają, ale powtarzają się wierzchołki. Dwa cykle (gdy nie nakładamy na nie warunku, by każdy wierzchołek występował w nich raz) możemy połączyć w dłuższy cykl. Łącząc wszystkie otrzymujemy cykl Eulera. --- Oczywiście powyższe to wyjaśnienie dowodu, a nie jego ścisłe przedstawienie.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj