Matematické Fórum

jirinaK · 16. 12. 2007 14:18

V grafu G s minimálním stupněm >= 2 existuje kružnice délky alespoň (velikost minimálního stupně) + 1. Dokažte.

Dělala bych to indukcí: Označím si "d" minimální stupeň grafu G. Začnu ve vrchole se stupněm d. Tady mam d možností, po jaké hraně jít dál. Následně mám alespoň d-1 možností, po jaké hraně jej opustit. V následujícím vrcholu mám přirozeně alespoň d-2 možností, kam z něj odejít. A tak dále, až se dostanu do místa, kde budu mít jen jednu možnost a následně aspoň d-d možností, což je nula. Takových kroků je celkem d. Tím jsem dokázala, že v takovém grafu existuje cesta aspoň délky d. No a jak na d+1?

Ještě bych se chtěla zeptat, co je to graf s vyváženou orientací, nikde jsem to tu nenašla. Děkuji.

Kondr · 16. 12. 2007 18:38

Tak to už je skoro hotové, ne?
Vrcholům budeme přiřazovat čísla podle toho, v kolikátém kroku jsme daným vrcholem prošli počínaje 0.
Podle popsaného postupu dojdeme do vrcholu d. V dalších krocích platí, že pokud stojíme ve vrcholu k, můžeme jít nejvýše d-1 způsoby vytvořit kružnici délky 2 až d (tj. tím, že půjdeme do vrcholů k-d+1 až k-1). Tím pádem máme vždy alespoň 1 možnost, jak jít dál, aniž bychom takto "krátkou" kružnici vytvořili. Protože v nějakém kroku se musíme vrátit tam, kde jsme začali, existuje v naší cestě cyklus. Přitom to nemůže být cyklus délky nejvýše d, takže jsme hotovi.

Czechtim · 18. 12. 2007 20:13

ja mam podobny "problem"
Dokažte, že je-li pro daný graf δ(G)≥2, potom G obsahuje cyklus. (δ velikost minimalniho stupne grafu δ(G)).

Napada me jedine nejak slovne to popsat, ze kdyz minimalni stupen 2, tak minimalni pocet vrcholu je 3 a na 3 vrcholech dosahnu minimalniho stupne vrcholu 2 jedine vytvorenim cyklu a pri vice vrcholech totez jedine cyklem a pokud by byl stupen vrcholu vetsi jak 2, pak jedine pridanim hrany uvnitr cyklu nebo vytvorenim noveho cyklu "vne" puvodniho cyklu.

Dalo by so to povazovat za matematicky dukaz, kdybych to nejak "lepe" zformuloval? Popr. jak by to slo matematicky zapsat? :)

Lishaak · 18. 12. 2007 20:36

Tvuj napad neprojde, protoze bys musel ukazat, ze timhle postupem vyrobis vsechno grafy, ktere splnuji podminku v zadani o to jsi nedokazal.

Presnejsi slovni dukaz:

Zacnu v libovolnem vrcholu x1. Oznacim ho jako navstiveny a z neho se vydam hranou (stupen je aspon 2, takze takova hrana vzdy existuje) do vrcholu x2. Ten oznacim jako navstiveny a jdu do x3. A tak porad dal. Kazdy vrchol ma stupen aspon dva, takze z neho vzdy vede hrana jina nez ta, kterou jsem prisel. Takhle ale namuzu pokracovat do nekonecna, protoze mam jenom konecne vrcholu. Drive nebo pozdeji se musim vratit do vrcholu, ktery uz je oznaceny, to znamena uz jsem v nem byl. Tim jsem nasel kruznici.

Kondr · 18. 12. 2007 20:36

Ha, Lishaak mě předběhl, ale stejně sem svou formulaci pošlu:

Pro spor předpokládejme, že v takovém grafu žádná kružnice není, tj. žádný tah neobsahuje kružnici. Pak ale délka tahu nepřekročí počet vrcholů grafu a existuje proto nejdelší tah. Protože koncový vrchol nejdelšího tahu má stupeň 2, jde tento tah prodloužit, což je spor s předpokladem, že je uvažovaný tah nejdelší.

Toto je takzvaná "extremní metoda" důkazu a v diskrétní matematice se hojně využívá.

Czechtim · 19. 12. 2007 08:01

A diky moc, jste borci.

Jenda1996 · 08. 01. 2008 09:27

Zdravím,

mohl by prosim Vás někdo nastínit, jak by se to řešilo, pokud bychom uvažovali NEJDELSI cestu
v grafu P=v_1,v_2,...,v_k. Vite, ze deg(v_k) [nebo deg(v_1)] je vetsi nebo rovno 2.

Děkuji moc.

Matematické Fórum

#1 16. 12. 2007 14:18

Důkaz existence kružnice v grafu

#2 16. 12. 2007 18:38

Re: Důkaz existence kružnice v grafu

#3 18. 12. 2007 20:13

Re: Důkaz existence kružnice v grafu

#4 18. 12. 2007 20:36

Re: Důkaz existence kružnice v grafu

#5 18. 12. 2007 20:36

Re: Důkaz existence kružnice v grafu

#6 19. 12. 2007 08:01

Re: Důkaz existence kružnice v grafu

#7 08. 01. 2008 09:27

Re: Důkaz existence kružnice v grafu

Zápatí