Matematické Fórum

prakovce · 20. 05. 2010 17:37

Potrebovala by som pomocť s následujucimi tvrdeniami :

1) Každé dve najdlhšie cesty v súvislom grafe majú spoločný vrchol.
2) Každý bipartitný d-regulárny graf (d>1) obsahuje 2-faktor.
3) Koľko je triangulácií konvexného n-uhelníka?
4) Nech sú hrany grafu K9 ofarbené červenou a modrou. Dokážte, že v tomto grafe K9 existuje buď červený C4, alebo modrý C3.
5) G je vrcholovo 3-súvislý graf a y,x sú jeho vrcholy.Existuje v G kružnica, ktorá prechádza y a neprechádza x ??

petrkovar

↑ prakovce:Zkusme napovědět:
1) sporem
2) Podle Hallovy věty daný graf obsahuje 1-faktor, a...
3) Pod heslem Catalanova čísla nebo Catalan numbers se toho dá najít opravdu hodně
4) první možnost: v alespoň jedné barvě musí existovat vrchol stupně 4. podívejme se na jeho sousedy.
Jiný způsob, těžší, jen jako hvězdičkový: graf na devíti vrcholech nebo jeho doplněk musí být neplanární (toto není triviální výsledek). Jaké neplanární grafy na devíti vrcholech mohou být podle Kuratovského věty? Může některý z nich mít obvod 5?
5) To je nějak podezřele lehké, pokud si uvědomíme, že K_6 je vrcholově 3-souvislý graf. Co teprve K_4? Tipnul bych si to na chybu v zadání.
Mimochodem: z jaké školy a jaký studijní obor řeší takové otázky?

prakovce · 22. 05. 2010 09:33

↑ petrkovar:

Matfyz ;-)

Ja väčšinou keď mám nieaké podobné tvrdenia tak dokážem určiť či to platí, neplatí a tak, ale keď to mám dokázať tak si už neviem rady :-D Skúsim to teda s nápovedou, čo si mi dal a keď tak sa ešte ozvem :-)

Zatiaľ díky

Matematické Fórum

#1 20. 05. 2010 17:37

Dokazy viet o grafoch

#2 20. 05. 2010 20:59 — Editoval petrkovar (20. 05. 2010 21:00)

Re: Dokazy viet o grafoch

#3 22. 05. 2010 09:33

Re: Dokazy viet o grafoch

Zápatí