Matematické Fórum

prakovce · 09. 02. 2010 09:33

Ahoj, potrebovala by som pomocť s dvoma príkladmi na grafy.
1) "Mějme dán rovinný graf G, jehož všechny stupně jsou alespoň 5. Dokažte, že nutně musí mít alespoň 12 vrcholů."
2) "Mějme dán souvislý graf G. Dokažte, že pro každou hranu e /z/ E(G) existuje kostra K grafu G, která hranu e obsahuje."

Wotton · 09. 02. 2010 10:08 — Editoval Wotton (09. 02. 2010 10:09)

Zdravím,

1) Víme že v roviném grafu platí nerovnost $|E|\leq 3|V|-6$ Protože všechny vrcholy jsou alespon stupně 5, tak musí platit nerovnost $\frac{5|V|}{2}\leq|E|$ To když spojíme tak máme $\frac{5|V|}{2}\leq 3|V|-6$ . Zbytek už zvládneš sama.

2) Zvolme si hranu (u;v) v G. Mějme F kostru grafu G takovou že neobsahuje hranu (u;v). Nyní musí vést z u do v cesta v F. Když na této cestě odstraníme libovolnou hranu, tak se nám kostra F rozpadne na 2 komponenty. Když k těmto komponentám přídáme hranu (u;v), tak nám vznikne graf F' který je kostrou grafu G.

petrkovar · 09. 02. 2010 21:04

↑ Wotton:U 2) navrhuji alternativu. Zvolíme libovolnou kostru F. Pokud hranu e obsahuje, jsme hotovi. Pokud ji F neobsahuje, tak F s přidanou hranou e obsahuje právě jeden cyklus/kružnici (cesta mezi u a v spolu s hranou e - navic je to věta, která se objevuje ve většině učebnic). Z toho cyklu vynecháme libovolnou hranu různou od e a dostaneme souvislý acyklický faktor, čili kostru.

petrkovar · 09. 02. 2010 21:07

↑ prakovce:Mimochodem, to tvrzení nejde zesílit. Vskutku existuje 5-pravidelný graf na 12 vrcholech. Jaký?

Wotton · 12. 02. 2010 13:19

↑ petrkovar:

Autor skryl část textu. Zobrazit/skrýt!

petrkovar · 12. 02. 2010 17:25

↑ Wotton:Ano, je to tak.

prakovce · 04. 03. 2010 18:51

Dakujem vsetkym za pomoc. Sice neskoro, ale predsa :-)

Matematické Fórum

#1 09. 02. 2010 09:33

Pomoc s grafmi

#2 09. 02. 2010 10:08 — Editoval Wotton (09. 02. 2010 10:09)

Re: Pomoc s grafmi

#3 09. 02. 2010 21:04

Re: Pomoc s grafmi

#4 09. 02. 2010 21:07

Re: Pomoc s grafmi

#5 12. 02. 2010 13:19

Re: Pomoc s grafmi

#6 12. 02. 2010 17:25

Re: Pomoc s grafmi

#7 04. 03. 2010 18:51

Re: Pomoc s grafmi

Zápatí