Doplňky stromů

Úloha číslo: 4086

Najděte všechny stromy \(T\), jejichž doplňkem je také strom. Zdůvodněte, že jste na žádný nezapomněli.

  • Řešení

    Protože pro \(n=|V_T|\) platí \(n=|E_T|+1=|E_{\bar T}|+1\) a \(|E_T|+|E_{\bar T}|=\binom{n}2\), musí \(n\) splňovat \(2n-2=\frac12(n^2-n)\), tedy \(n^2-5n+4=0\). Tato kvadratická rovnice má dvě nezáporná celočíselná řešení:

    • \(n=1\), odpovídající strom je \(K_1\) a
    • \(n=4\), odpovídající strom je \(P_4\). Ostatní stromy na čtyřech vrcholech nevyhovují, jak zjistíme rozborem případů.
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze