Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Cykle grafów

Strona 1 z 1

[ Posty: 2 ]

Autor

Wiadomość

maybe

Tytuł: Cykle grafów

Napisane: 30 sty 2016, o 01:11

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

TrzyRazyCztery Offline

Tytuł: Cykle grafów

Napisane: 30 sty 2016, o 15:12

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

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 2 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
kolorowanie grafów - zadanie 3	flashion	0
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

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]