Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

Spanning trees

Task number: 2609

Use determinant to calculate the number of spanning trees of the following graphs:

  • Variant

    the given graph
  • Solution

    The Laplace’s matrix of the graph is

    LG=(4111114111113101113011002)

    By the theorem on the number of spanning trees

    κ(G)=det
    = \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 .

    It is possible to verify the result by a listing of all spanning trees: K_4 has 16 spanning trees and each has two options to join the top vertex (the left or the right edge) – in total 32 possibilities. Otherwise the spanning tree contains both edges incident with the top vertex and then we have 4 options that contain the bottom edge an 4 that do not.

  • Answer

    The graph has 40 spanning trees.

  • Variant

    the given graph 2
  • Solution

    Laplace’s matrix: L_G= \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}

    Number of spanning trees: \kappa(G)=|L_G^{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

  • Answer

    The graph has 960 spanning trees.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email