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 
 Cykle w grafie  phnxck  0
 Iloczyn kartezjański grafów.  mike866  1
 Teoria grafów - zadanie 12  Antia  1
 Kilka zadań z teorii grafów  patryk007  0
 Dowód zachowania stopnia wierzchołka w izomorfizmie grafów  Renq77  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl