Sbírka matematických úloh

Počet koster

Úloha číslo: 2587

• Varianta

  

• Ř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í.

• Odpověď

  Graf má 40 koster.

• Varianta

  

• Řešení

  Laplaceova matice: \(L= \begin{pmatrix} 5 & -2 & 0 & -1 & 0 & -2 \\ -2 & 5 & -2 & 0 & -1 & 0 \\ 0 & -2 & 5 & -2 & 0 & -1 \\ -1 & 0 & -2 & 5 & -2 & 0 \\ 0 & -1 & 0 & -2 & 5 & -2 \\ -2 & 0 & -1 & 0 & -2 & 5\\ \end{pmatrix} \)

  Počet koster: \( \kappa(G)=|L^{11}|= \begin{vmatrix} 5 & -2 & 0 & -1 & 0 \\ -2 & 5 & -2 & 0 & -1 \\ 0 & -2 & 5 & -2 & 0 \\ -1 & 0 & -2 & 5 & -2 \\ 0 & -1 & 0 & -2 & 5\\ \end{vmatrix} = 960 \)

• Odpověď

  Graf má 960 koster.