8 Distance Matrix of a Tree ぱらぱらめくる『Graphs and Matrices』

  • 木のDistance matrixの場合、det D = (-1)^{n-1} (n-1)2^{n-2}
  • 木でないグラフのDistance matrixの場合は、サイクルとそうでない部分(木)に分けて行く
  • 木のDistance matrixのLaplacian、固有値を考えることで有用な性質がある