szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Cykle grafów
PostNapisane: 30 sty 2016, o 01: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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
 Tytuł: Cykle grafów
PostNapisane: 30 sty 2016, o 15: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 
 izomorfizm grafów  jogurtcytrynowy  1
 Teoria grafów - drzewa  Arecki123  1
 Ile jest grafów na zbiorze  iie  3
 Ilość grafów etykietowanych.  akermann1  5
 [GRAFY] Ile jest grafów  ematyk  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl