Matematické Fórum

Koube · 04. 12. 2011 13:18

Mějme kompletní graf $K2_n$ , kde $n \in N$ . Kolik nejménì hran z něj musíme odebrat, aby vznikl nejvýše hranově $(2n - 2)$ -souvislý graf? Své tvrzení zdůvodněte!

Moje zdůvodnění se opírá o scripta pana profesora Kováře konkrétně příklad 1.12/1.14 kde //jestli jsem to dobře pochopil je to aspon z části vysvětleno //

Budeme vychazet ze vztahu pro Stupně vrcholù kde každy vrchol grafu $K_n$ je sousední se všemu ostatními vrcholy,a stupen každého vrcholu je $n-1$ .
To využijem i pro náš příklad kde $K2_n$ vrcholu musí vytvořit $(2n - 2)$ stupen vrcholu.
Jestliže bude n=2,tak $K2_n$ = $K4$ kde stupen každeho vrcholu bude $2*2-1$ = $3$ stupòova posloupnost (3,3,3,3),pro to aby jsme dostali stupen vrcholu $(2n - 2)$ je potřeba odebrat právě $n$ hran aby vznikl stupen vrcholu $(2n - 2)$ stupnova posloupnost (2,2,2,2)

petrkovar · 04. 12. 2011 13:38

Ne, zdůvodnění není správně. Zaměňujete pojmy: stupeň vrcholů v grafu a stupeň souvislosti grafu. O stupních souvislosti v první kapitole mého skritpta není psáno a další kapitoly nejsou dopsány. Avšak ve skriptech doc. Hliněného zde na straně 60 najdete definici a několik příkladů, ve cvičení zde najdete na straně 48 několik příkladů. Podrobný komentář byl na přednášce.

Není pravda, že je potřeba odebrat právě n hran.

Koube · 04. 12. 2011 17:15 — Editoval Koube (04. 12. 2011 17:23)

Jsem naprosto zoufaly takže zkusím výstřel do tmy.

Jestliže mám $K_n$ souvislý graf tak jeho hrany se určují podle $n-1$

Takže když mám $K_2n$ souvisly graf tak jeho hrany se určují podle $(2n-2)$
Když zvětšujem n tak se vždy zvýší i stupen vrcholu,a podle mě nemusíme odebrat žádnou hranu,protože
$K_2n$ je hranově $(2n - 2)$ -souvislý graf

petrkovar · 04. 12. 2011 17:30

↑ Koube:Reaguje na předchozí příspěvek. To je opravdu výstřel do tmy. Co to znamená "hrany se určují podle $n-1$ "?

Soustřeďme se na hranovou souvislost kompletního grafu. Jaká je hranová souvislost $K_n$ ? A proč?
Je graf $K_6$ hranově 1-souvislý? A proč?
A je hranově 2-souvislý? hranově 3-souvislý? hranově 4-souvislý?hranově 5-souvislý?hranově 6-souvislý? hranově 7-souvislý? A u každé odpovědi vysvětlete proč.

Koube · 04. 12. 2011 17:42

Hranová souvislost $Kn$ je $n-1$ .

K další otazce se nebudu vyjadřovat i když věřím že by mi to pomohlo,ale zkusím

$K_2n$ je vždy $2n-1$ souvislý takže si myslím že když odeberu jednu hranu vznikne $2n-2$ hranově souvislý graf

Zkusil jsem se na to podívat ještě jednou pomocí Mengerovy věty,tak doufám že to je pravda

tarantulka · 04. 12. 2011 18:38

↑ Koube:
ja suhlasim, aj mne to tak vyslo, skusala som aj tu Mengerovu vetu

ak to tak nie je tak uz neviem ako

Matematické Fórum

#1 04. 12. 2011 13:18

Teorie Grafu proj.č.7

#2 04. 12. 2011 13:38

Re: Teorie Grafu proj.č.7

#3 04. 12. 2011 14:20 Příspěvek uživatele Koube byl skryt uživatelem Koube.

#4 04. 12. 2011 17:15 — Editoval Koube (04. 12. 2011 17:23)

Re: Teorie Grafu proj.č.7

#5 04. 12. 2011 17:30

Re: Teorie Grafu proj.č.7

#6 04. 12. 2011 17:42

Re: Teorie Grafu proj.č.7

#7 04. 12. 2011 18:38

Re: Teorie Grafu proj.č.7

Zápatí