Počet listů v (1,3)-stromu

Úloha číslo: 4077

Mějme strom, který má \(l>0\) listů a \(v\) vnitřních vrcholů, přičemž každý vnitřní vrchol má stupeň 3. Dokažte, že vždy platí \(l = v+2\).

  • Řešení

    Přímo, spočítáme všechny hrany, a vrcholy:

    \(|V_G|=l+v\),

    \(2|E_G|=l+3v\) (princip sudosti).

    Dosazením do \(|V_G|=|E_G|+1\) máme \(l+v =\frac12 (l+3v)+1\), z čehož úpravou dostaneme \(l = v+2\).

    Alternativně indukcí podle počtu vnitřních vrcholů.

    Pro \(v=0\), \(l=2\) jde o strom \(K_2\) a tvrzení platí.

    Vezměme libovolný vrchol stupně tři a rozdělme jej na tři listy. Tím vzniknou tři stromy, splňující indukční předpoklad. Pro \(i=1{,}2,3\) označme \(l_i\) a \(v_i\) počty listů a vnitřních vrcholů v \(i\)-tém vzniklém stromě.

    Platí: \(v=v_1+v_2+v_3+1=(l_1-2)+(l_2-2)+(l_3-2)+1=l_1+l_2+l_3-5=l-2\).

    První a poslední rovnosti odpovídají situaci, kdy rozdělením vzniknou z jednoho vnitřního vrcholu tři listy.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze