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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
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 
 Policz wszystkie izomorfizmy podanych grafów  dram  0
 zadanko z teorii grafów :-)  Kardana  2
 Zliczanie grafów, sprawdzenie poprawności rozwiązania.  donmaciej  9
 Ile jest grafów.  bLask  2
 twierdzenie dotyczące grafów planarnych  dela  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl