Počet koster

Úloha číslo: 2587

Pomocí determinantu určete počet koster následujícího grafu:

daný graf
  • Řešení

    Laplaceova matice grafu je

    \( L=\begin{pmatrix} 4 & -1 & -1 & -1 & -1 \\ -1 & 4 & -1 & -1 & -1 \\ -1 & -1 & 3 & -1 & 0 \\ -1 & -1 & -1 & 3 & 0 \\ -1 & -1 & 0 & 0 & 2 \\ \end{pmatrix} \)

    Podle věty o počtu koster je

    \(\kappa(G)=\det(L^{1{,}1})= \begin{vmatrix} 4 & -1 & -1 & -1 \\ -1 & 3 & -1 & 0 \\ -1 & -1 & 3 & 0 \\ -1 & 0 & 0 & 2 \\ \end{vmatrix} = \begin{vmatrix} 4 & -1 & -1 & -1 \\ -1 & 3 & -1 & 0 \\ -1 & -1 & 3 & 0 \\ 7 & -2 & -2 & 0 \\ \end{vmatrix} = \begin{vmatrix} -1 & 3 & -1 \\ -1 & -1 & 3 \\ 7 & -2 & -2 \\ \end{vmatrix} \)
    \( = \begin{vmatrix} -1 & 3 & -1 \\ 0 & -4 & 4 \\ 0 & 19 & -9 \\ \end{vmatrix} =-4 \begin{vmatrix} -1 & 1 \\ 19 & -9 \\ \end{vmatrix} =-4(9-19)=40 \).

    Lze ověřit, že je tomu skutečně tak výčtem všech koster: \(K_4\) má 16 koster a ke každé z nich jsou dvě možnosti, jak připojit horní vrchol (zprava, zleva) – celkem 32 možností. Jinak kostra obsahuje celou stříšku a v tom případ máme 4 možnosti, které obsahují základnu, a 4, které ji neobsahují.

  • Výsledek

    Graf má 40 koster.

Obtížnost: Středně těžká úloha
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze