Matematyka dyskretna, zadanie nr 4774
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
brightnesss post贸w: 113 |  2016-08-13 13:40:57Witam, 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