Matematické Fórum

veadet · 20. 04. 2015 20:00

Dobry podvecer. Neviem si pomoct s ulohou z oblasti teorie grafov- Dokazte ze vsetky kostry daneho grafu maju rovnaky pocet hran. Neviem, ako na to. Mohlo by mi pomoct to, ze kostra je suvisly acyklicky faktor grafu a z toho vieme ze neobsahuje kruznicu?

byk7 · 20. 04. 2015 20:32

http://forum.matweb.cz/viewtopic.php?id=83127

veadet · 20. 04. 2015 20:38 — Editoval veadet (20. 04. 2015 20:41)

v tom vlakne co je $V$ a $E$ ? Pojem "invariant" sme este nemali, da sa to dokazat bez neho? Prikladne mi ukazte nejaku vhodnu definiciu tohto pojmu.

byk7 · 20. 04. 2015 20:44

$V$ je množina vrcholů, $E$ je množina hran, invariantu se neboj, prostě řekni, že při libovolné kostře se hodnota výrazu $|V|-1$ nezmění a díky tomu, že je to strom, tak...

veadet · 20. 04. 2015 20:45

no aj tak by som ten pojem "invariant" mal poriadne zadefinovany.

byk7 · 20. 04. 2015 20:51

http://cs.wikipedia.org/wiki/Invariant_(matematika)

Ale jak říkám, není nutné ten pojem při důkazu použít.

veadet · 20. 04. 2015 22:16

A ako by bez invariantu dokaz vyzeral?

byk7 · 20. 04. 2015 22:22

Kostra $K$ grafu $G$ je strom, který obsahuje všechny vrcholy (takže $V(G)=V(K)$ ), a pro stromy platí $|E|=|V|-1$ . Protože se pro jakoukoliv kostru daného grafu hodnota $|V(K)|-1=|V(G)|-1$ nemění, nemění se ani hodnota $|E(K)|$ .