Matematické Fórum

jaj · 05. 05. 2010 13:48

Prosim o radu - jak dokazat, že každý 3 regulární souvislý bipartitní graf je vrcholově 2-souvislý, děkuji

petrkovar · 05. 05. 2010 15:57

↑ jaj:Navrhuji postupovat sporem.
Kdyby $x$ byla artikulace grafu $G$ , tak v nesouvislém podgrafu $G-x$ najdeme jednu komponentu s právě jedním vrcholem stupně 2 a ostatními vrcholy stupně 3 (proč?). Toto pozorování ihned vede ke sporu, pokud si uvědomíme, že tato komponenta je také bipartitní a jaký je součet stupňů v každé partitě této komponenty.

jaj · 06. 05. 2010 09:33

↑ petrkovar: děkuji, nejak si nedokazu predstavit tu vrcholovou souvislost - vim ze je to velikost minimalniho vrcholoveho rezu a rez je snad to ze se odebere vrchol a graf nebude souvisly

jinak teda pocitam s tim ze x (hrana) v grafu a kdyz x odeberu - tak mi znikne nesouvisly graf - ktery bude mit 1 vrchol stupne 2 a ostatni stupne 3 a nevim teda s tou vrcholovou souvislostí - co s tim

petrkovar

↑ jaj:Vrcholová souvislost je číslo, které udává nejmenší počet VRCHOLŮ, které z grafu musíme odebrat, aby se stal nesouvislým. Množina takových vrcholů se nazývá vrcholový řez. Třeba cesta $P_n$ (n>2) je 1-souvislá. Stačí odebrat jediný vrchol a bude nesousvislý graf. Naproti tomu cyklus $C_n$ (n>3) je 2-souvislý.
Podobně je definovaná hranová souvislost.
Pozor! $x$ není hrana, ale VRCHOL. Artikulace je vrchololový řez s jediným vrcholem. Aby se argumentovalo hranou, musela by se použít další věta, kterou nevím, zda máte dokázanou. (ta věta říká, že pro 3-regulární grafy se hodnota hranové a vrcholové souvislosti rovnají)

(Pozn.:S výstavbou pojmu "k-souvislý graf" a grafová "k-souvislost" je to mírně komplikovanější, záleží na definici v tom kterém předmětu. Ale pro řešení problému stačí, co jsem tu napsal.)

jaj · 06. 05. 2010 16:48

↑ petrkovar: tak mam bipartitní graf K3,3 - což je 3 regulární graf a odeberu z něho 2 vrcholy, ale je porad souvisly - tak mi vychazi ze neni 2-souvisly, ale musim odebrat 3 vrcholy, tak je 3 souvisly, ale mam dokazat ze je 2 souvisly, nevim, kde delam chybu

petrkovar · 06. 05. 2010 21:53

↑ jaj:Doporučuji pečlivě přečíst definice 2-souvislosti a 2-souvislého grafu. (To je ta moje modrá poznámka)
$K_{3,3}$ je vrcholově 3-souvislý, ale i 2-souvislý, 1-souvislý. Ale vrcholová souvislost je 3. takže žádná chyba není.

jaj · 06. 05. 2010 23:15

↑ petrkovar:proste to nechapu, je K3,3 3-regularní a 3-souvislý, každý 3 regulární graf ma podle toho co mam dokazat byt 2 souvisly, nebo K3,3 neni 3-regularni, pochopila jsem ze 3 regularni je tehdy, kdyz z kazdeho vrcholu vedou tri hrany

petrkovar · 07. 05. 2010 07:29

↑ jaj:To, že je graf vrcholově 3-souvislý, nevylučuje že je 2-souvislý. Naopak. k-souvislý graf je také (k-1)-souvislý, (k-2)-souvislý atd.
Jiný pojem je vrcholová souvislost. Vrcholová souviislost grafu je jednoznačně určené číslo. Takže je-li vrcholová souvislost grafu $K_{3,3}$ rovna 3, tak je $K_{3,3}$ (mimo jiné) 2-souvislý. Oba pojmy zní podobně, ale jijich význam je jiný. Doporučuji nalistovat v přednáškách...

jaj · 09. 05. 2010 20:56

Ja chapu že když je graf 3- souvisly, tak je i 2 souvisly, ale 2 souvislý bipartitni graf uz neni 3 regularni, ale 2 regularni, nevim jak to mam dokazat, pokud by jste mi to mohli nejak vysvetlit, popripade ukazat naznak vice dukazu bylo by to lepsi pro pochopeni, jinak moc dekuji

petrkovar · 09. 05. 2010 22:42

jaj napsal(a):
ale 2 souvislý bipartitni graf uz neni 3 regularni

Některý ano, když do cyklu $C_8$ přidáme hrany $v_1v_3$ , $v_2v_4$ , $v_5v_7$ , $v_6v_8$ .
Dokonce existují 1-souvislé 3-regulární grafy. Stačí, aby graf obsahoval most.

jaj · 09. 05. 2010 22:47

↑ petrkovar: co je to most, tento termin vubec neznam, ale to ma platit pro - viz tvrzeni kazdy 3 bipartitni graf ma byt 2 souvisly a ne jen C8, a ten dukaz udelam jak - např. muzu odebirat tak dlouho vrcholy az se mi bipartitni graf rozpadne a zjistim ze je 2 souvisly

petrkovar · 10. 05. 2010 21:58

↑ jaj:Most je hranový řez velikosti 1.
Neboli: most v grafu je taková hrana v sovislém grafu, že jejím odebráním dostaneme nesouvislý graf.
Třeba ve stromu je každá hrana mostem. V cyklu není žádný most.
A v 2-souvislém grafu není žádný most.

jaj · 11. 05. 2010 13:05

dekuji, ale ja porad nevim jak to dokazat, kdyz to delam sporem, tak neco mi tam musi neplatit, nevim co

petrkovar · 11. 05. 2010 14:37

↑ jaj:Dostali jsme se do fáze, kdy si myslím, že odpověď už je k nalezení v předchozích poznámkách (zejména v mé první odpovědi).
Jak vypadá rozepsaná část důkazu?

jaj · 13. 05. 2010 14:12

↑ petrkovar:dekuji, uz mam dokazano

Matematické Fórum

#1 05. 05. 2010 13:48

Souvislost grafu

#2 05. 05. 2010 15:57

Re: Souvislost grafu

#3 06. 05. 2010 09:33

Re: Souvislost grafu

#4 06. 05. 2010 09:45 — Editoval petrkovar (06. 05. 2010 09:47)

Re: Souvislost grafu

#5 06. 05. 2010 16:48

Re: Souvislost grafu

#6 06. 05. 2010 21:53

Re: Souvislost grafu

#7 06. 05. 2010 23:15

Re: Souvislost grafu

#8 07. 05. 2010 07:29

Re: Souvislost grafu

#9 09. 05. 2010 20:56

Re: Souvislost grafu

#10 09. 05. 2010 22:42

Re: Souvislost grafu

jaj napsal(a):

#11 09. 05. 2010 22:47

Re: Souvislost grafu

#12 10. 05. 2010 21:58

Re: Souvislost grafu

#13 11. 05. 2010 13:05

Re: Souvislost grafu

#14 11. 05. 2010 14:37

Re: Souvislost grafu

#15 13. 05. 2010 14:12

Re: Souvislost grafu

Zápatí