Matematické Fórum

Empair · 26. 01. 2016 22:19

Dobrý podvečer

pokouším se vyřešit jeden projekt z DIM a mám zadanou obecnou otázku. Kolik vrcholů by měl nejmenší graf se 3mi disjukními kostrami?

I když už jsem pokreslil 10 listů nedaří se mi najít takový graf. Mohli by jste mě nasměrovat?

petrkovar · 27. 01. 2016 00:02

Kolik má mít kostra hran vzhledem k počtu vrcholů n?
Kolik hran se vejde do grafu na n vrcholech?
Mají-li být kostry 3, bude z toho nerovnice. Prozradím, že řešení je ostré, tj. Existuje takový graf s teoreticky minimálním počtem vrcholů.

Empair · 27. 01. 2016 09:34 — Editoval Empair (27. 01. 2016 09:44)

Děkuji za radu.

Svoji úvahu jsem tedy dle rady

n - počet vrcholů

1) Kostra má n-1 hran vzhledem k počtu vrchulů
2) Do grafu se vejde $C_{2}(n)$ hran

Vytvořil jsem z toho nerovnice, u které mi vyšlo 1 a n > 6.

U grafu s jedním vrcholem je to zajímavé, tam bude neomezené množství koster ale všechny totožné.

Tudíž nejmenší počet vrcholů pro graf se 3mi disjkuními kostrami je 7.

Hned jsem ho i nakreslil a opravdu jsem je tam našel.

Pro ověření dávám obrázek.

Postupoval jsem správně?

petrkovar · 27. 01. 2016 10:02

Téměř správně:)
Nerovnice není správně vyřešena a na obrázku růžovou barvou není kostra.
Hlavní myšlenka však je správně.

Empair · 27. 01. 2016 11:36

nechal jsem se unést, že jsem našel 3 kostry a udělal jsem z poslední cyklus :)

nerovnici vyřeším znova snad už neudělám chybu
teďka se musím zase věnovat trochu práci

Zatím děkuji.

Empair · 27. 01. 2016 13:29

Přepočítal jsem znova nerovnici

ale nedošel jsem k jinému výsledku ... jen se mi dosazení podařilo vyloučit 1

mám tam numerickou chybu nebo úvahu?

Empair · 27. 01. 2016 16:03

K tomuto tématu mám ještě jeden úkol a tak bych chtěl zkonzultovat i ten.

Zadání:

Moje úvaha je taková:
Nejmenší stupeň grafu se třemi disjuktnimi kostrami je 3. V nejmenší grafu se který obsahuje 3 disjuktní kostry je nejmenší stupeň vrcholu 4. Pro pokus o nalezení musíme minimální graf rozšít. Při rozšíření na 8 vrcholů se již podaří najít vrchol se stupňem 3.

Dá se to považovat za splnění zadání? Nebo je k tomu třeba dojít jinou cestou? Ak ano můžete mi zase poradit jakou?

Xellos · 27. 01. 2016 23:32

↑ Empair:

Preco ostra nerovnost?

↑ Empair:

Minimalny stupen: hej. Staci okomentovat ze preco 3 a najst priklad (ten staci najst tak ze nakreslis lubovolny graf s 3 disj. kostrami, pridas k nemu vrchol a 3 hrany z neho - tie mozes potom priradit k 3 roznym kostram).

Empair · 28. 01. 2016 08:48 — Editoval Empair (28. 01. 2016 08:49)

↑ Xellos:
aha to je vlastně pravda ... ta nerovnost nemusí být ostrá ... nevím proč dělám takové chyby

Udělal jsem opravu.

Jen se trochu trápím na výsledkem 1. Graf o jednom vrcholu je taky řešení?

Matematické Fórum

#1 26. 01. 2016 22:19

Nejmenší Graf se 3mi disjunktními kostrami

#2 27. 01. 2016 00:02

Re: Nejmenší Graf se 3mi disjunktními kostrami

#3 27. 01. 2016 09:34 — Editoval Empair (27. 01. 2016 09:44)

Re: Nejmenší Graf se 3mi disjunktními kostrami

#4 27. 01. 2016 10:02

Re: Nejmenší Graf se 3mi disjunktními kostrami

#5 27. 01. 2016 11:36

Re: Nejmenší Graf se 3mi disjunktními kostrami

#6 27. 01. 2016 13:29

Re: Nejmenší Graf se 3mi disjunktními kostrami

#7 27. 01. 2016 16:03

Re: Nejmenší Graf se 3mi disjunktními kostrami

#8 27. 01. 2016 23:32

Re: Nejmenší Graf se 3mi disjunktními kostrami

#9 28. 01. 2016 08:48 — Editoval Empair (28. 01. 2016 08:49)

Re: Nejmenší Graf se 3mi disjunktními kostrami