szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Cykle grafów
PostNapisane: 30 sty 2016, o 02:11 
Użytkownik

Posty: 21
Uzasadnij że jeżeli każdy z dwóch różnych cykli grafu G zawiera krawędź e, to w G istnieje cykl, który nie zawiera krawędzi e.

Obrazek

Graficzne rozwiązanie prezentuje się tak, ale szczerze mówiąc nie do końca rozumiem tego dowodu.
Góra
Mężczyzna Offline
 Tytuł: Cykle grafów
PostNapisane: 30 sty 2016, o 16:12 
Użytkownik

Posty: 101
Lokalizacja: Wro
Ja bym to robił mniej wiecej tak: krawedz e łączy w tym grafie jakies 2 wierzchołki, oznaczmy je jako u,v Z tego ze skoro sa 2 różne cykle zawierające krawędz e (różnią sie przynajmniej jedną krawędzią) wynika że mamy na pewno 2 cykle, nazwijmy je A i B takie że A: u  \xrightarrow{a_{0}} ... \xrightarrow{a_{i}}v \xrightarrow{e} u oraz B: u  \xrightarrow{b_{0}} ... \xrightarrow{b_{i}}v \xrightarrow{e} u Wiec w szczególnosci możemy utworzyc cykl u  \xrightarrow{b_{0}} ... \xrightarrow{b_{i}}v  \xrightarrow{a_{i}} ... \xrightarrow{a_{0}} u Czyli cykl nie zawierający krawędzi e co należało udowodnić.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kilka zadań z grafów  gosienkaq  0
 Teoria grafów.  be-girl222  1
 Podział zbioru na cykle.  Richard del Ferro  7
 Drzewa i liście - teoria grafów  silvaran  1
 [Teoria grafów] Poprawny (?) dowód indukcyjny  matinf  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl