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.

Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019

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
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

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