行列木定理 (Kirchhoff's matrix tree theorem)
(include/emthrm/graph/matrix_tree_theorem.hpp)
spectral graph theory
行列木定理 (Kirchhoff’s matrix tree theorem)
無向グラフ $G$ の全域木の個数は $G$ のラプラシアン行列の任意の余因子に等しい。
$N$ 頂点のラベル付きの木の個数は $N^{N - 2}$ である。
行列木定理の特殊なときとして示せる。
Lindström–Gessel–Viennot lemma
有向非巡回グラフ $G$、頂点集合 $A = \lbrace a_1, a_2, \ldots, a_n \rbrace,\ B = \lbrace b_1, b_2, \ldots, b_n \rbrace$、可換環 $R$ 上の重み $w \colon E(G) \to R$ が与えられる。ただし有向パス $P$ に対して $\omega(P) \mathrel{:=} \prod_{e \in P} w(e)$ とおき、任意の $s, t \in V(G)$ に対して $e(s, t) \mathrel{:=} \sum_{\text{始点 } s \text{・終点 } t \text{ の有向パス } P} \omega(P)$ が well-defined であるとする。
以下を満たす $n$ 本のパスの組を $(P_1, P_2, \ldots, P_n)$ と記す。
ある $\lbrace 1, 2, \ldots, n \rbrace$ の置換 $\sigma$ が存在し、任意の $i \in \lbrace 1, 2, \ldots, n \rbrace$ に対して $P_i$ は始点 $a_i$・終点 $b_{\sigma(i)}$ の有向パスである。
$i \neq j$ を満たす任意の $i, j \in \lbrace 1, 2, \ldots, n \rbrace$ に対して $P_i$ と $P_j$ は点素である。
このとき
\[\det(M) = \sum_{(P_1, P_2, \ldots, P_n)} \mathrm{sgn}(\sigma) \prod_{i = 1}^n \omega(P_i)\]
が成り立つ。ただし $M$ は $m_{ij} \mathrel{:=} e(a_i, b_j)$ で定義される $n$ 次正方行列である。
特殊な場合として、任意の $e \in E(G)$ に対して $w(e) = 1$ が成り立つときを考える。このとき $e(s, t)$ は始点 $s$・終点 $t$ の有向パスの本数に等しい。
さらに $i < j,\ k < l$ を満たす任意の $i, j, k, l \in \lbrace 1, 2, \ldots, n \rbrace$ に対して、始点 $a_i$・終点 $b_l$ の有向パスと始点 $a_j$・終点 $b_k$ の有向パスが必ず交差するとき、任意の $(P_1, P_2, \ldots, P_n)$ に対応する置換 $\sigma$ は恒等置換のみとなる。すなわち始点 $a_i$ に対応する終点は必ず $b_i$ となる。
時間計算量
仕様
行列木定理
名前
戻り値
template <typename T, typename CostType>
T matrix_tree_theorem(const std::vector<std::vector<Edge<CostType>>>& graph, const T eps = 1e-8);
無向グラフ $\mathrm{graph}$ の全域木の個数
参考文献
https://www.slideshare.net/irrrrr/ss-25911553
行列木定理
http://www2.yukawa.kyoto-u.ac.jp/~kanehisa.takasaki/res/tsuda2021history.pdf
https://mizuwater0.hatenablog.com/entry/2018/11/25/233547
https://www.ioi-jp.org/camp/2017/2017-sp_camp-kumabe2.pdf
ケイリーの公式
Arthur Cayley: A theorem on trees, The Quarterly Journal of Pure and Applied Mathematics , Vol. 23, pp. 376–378 (1889).
http://joisino.hatenablog.com/entry/2017/08/20/200000
Lindström–Gessel–Viennot lemma
Ira Gessel and Gérard Viennot: Binomial determinants, paths, and hook length formulae, Advances in Mathematics , Vol. 58, No. 3, pp. 300–321 (1985). https://doi.org/10.1016/0001-8708(85)90121-5
https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma
https://suikaba.hatenablog.com/entry/2018/12/19/025636
https://www.ioi-jp.org/camp/2017/2017-sp_camp-kumabe2.pdf
https://twitter.com/kotatsugame_t/status/1411648290546851840
https://twitter.com/noshi91/status/1432074841675362304
https://atcoder.jp/contests/abc216/editorial/2561
Submissons
Depends on
Verified with
Code
#ifndef EMTHRM_GRAPH_MATRIX_TREE_THEOREM_HPP_
#define EMTHRM_GRAPH_MATRIX_TREE_THEOREM_HPP_
#include <algorithm>
#include <iterator>
#include <vector>
#include "emthrm/graph/edge.hpp"
#include "emthrm/math/matrix/determinant.hpp"
#include "emthrm/math/matrix/matrix.hpp"
namespace emthrm {
template < typename T , typename CostType >
T matrix_tree_theorem ( const std :: vector < std :: vector < Edge < CostType >>>& graph ,
const T eps = 1e-8 ) {
const int n = graph . size ();
if ( n == 1 ) [[ unlikely ]] return 1 ;
Matrix < int > laplacian ( n , n , 0 );
for ( int i = 0 ; i < n ; ++ i ) {
for ( const Edge < CostType >& e : graph [ i ]) {
++ laplacian [ e . src ][ e . src ];
-- laplacian [ e . src ][ e . dst ];
}
}
Matrix < int > cofactor ( n - 1 , n - 1 );
for ( int i = 0 ; i < n - 1 ; ++ i ) {
std :: copy ( std :: next ( laplacian [ i + 1 ]. begin ()), laplacian [ i + 1 ]. end (),
cofactor [ i ]. begin ());
}
return det ( cofactor , eps );
}
} // namespace emthrm
#endif // EMTHRM_GRAPH_MATRIX_TREE_THEOREM_HPP_
#line 1 "include/emthrm/graph/matrix_tree_theorem.hpp"
#include <algorithm>
#include <iterator>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template < typename CostType >
struct Edge {
CostType cost ;
int src , dst ;
explicit Edge ( const int src , const int dst , const CostType cost = 0 )
: cost ( cost ), src ( src ), dst ( dst ) {}
auto operator <=> ( const Edge & x ) const = default ;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/math/matrix/determinant.hpp"
#line 5 "include/emthrm/math/matrix/determinant.hpp"
#include <utility>
#line 1 "include/emthrm/math/matrix/matrix.hpp"
#line 5 "include/emthrm/math/matrix/matrix.hpp"
namespace emthrm {
template < typename T >
struct Matrix {
explicit Matrix ( const int m , const int n , const T def = 0 )
: data ( m , std :: vector < T > ( n , def )) {}
int nrow () const { return data . size (); }
int ncol () const { return data . empty () ? 0 : data . front (). size (); }
Matrix pow ( long long exponent ) const {
const int n = nrow ();
Matrix < T > res ( n , n , 0 ), tmp = * this ;
for ( int i = 0 ; i < n ; ++ i ) {
res [ i ][ i ] = 1 ;
}
for (; exponent > 0 ; exponent >>= 1 ) {
if ( exponent & 1 ) res *= tmp ;
tmp *= tmp ;
}
return res ;
}
inline const std :: vector < T >& operator []( const int i ) const { return data [ i ]; }
inline std :: vector < T >& operator []( const int i ) { return data [ i ]; }
Matrix & operator = ( const Matrix & x ) = default ;
Matrix & operator += ( const Matrix & x ) {
const int m = nrow (), n = ncol ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
data [ i ][ j ] += x [ i ][ j ];
}
}
return * this ;
}
Matrix & operator -= ( const Matrix & x ) {
const int m = nrow (), n = ncol ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
data [ i ][ j ] -= x [ i ][ j ];
}
}
return * this ;
}
Matrix & operator *= ( const Matrix & x ) {
const int m = nrow (), l = ncol (), n = x . ncol ();
std :: vector < std :: vector < T >> res ( m , std :: vector < T > ( n , 0 ));
for ( int i = 0 ; i < m ; ++ i ) {
for ( int k = 0 ; k < l ; ++ k ) {
for ( int j = 0 ; j < n ; ++ j ) {
res [ i ][ j ] += data [ i ][ k ] * x [ k ][ j ];
}
}
}
data . swap ( res );
return * this ;
}
Matrix operator + ( const Matrix & x ) const { return Matrix ( * this ) += x ; }
Matrix operator - ( const Matrix & x ) const { return Matrix ( * this ) -= x ; }
Matrix operator * ( const Matrix & x ) const { return Matrix ( * this ) *= x ; }
private:
std :: vector < std :: vector < T >> data ;
};
} // namespace emthrm
#line 8 "include/emthrm/math/matrix/determinant.hpp"
namespace emthrm {
template < typename T , typename U >
U det ( const Matrix < T >& a , const U eps ) {
const int n = a . nrow ();
Matrix < U > b ( n , n );
for ( int i = 0 ; i < n ; ++ i ) {
std :: copy ( a [ i ]. begin (), a [ i ]. end (), b [ i ]. begin ());
}
U res = 1 ;
for ( int j = 0 ; j < n ; ++ j ) {
int pivot = - 1 ;
U mx = eps ;
for ( int i = j ; i < n ; ++ i ) {
const U abs = ( b [ i ][ j ] < 0 ? - b [ i ][ j ] : b [ i ][ j ]);
if ( abs > mx ) {
pivot = i ;
mx = abs ;
}
}
if ( pivot == - 1 ) return 0 ;
if ( pivot != j ) {
std :: swap ( b [ j ], b [ pivot ]);
res = - res ;
}
res *= b [ j ][ j ];
for ( int k = j + 1 ; k < n ; ++ k ) {
b [ j ][ k ] /= b [ j ][ j ];
}
for ( int i = j + 1 ; i < n ; ++ i ) {
for ( int k = j + 1 ; k < n ; ++ k ) {
b [ i ][ k ] -= b [ i ][ j ] * b [ j ][ k ];
}
}
}
return res ;
}
} // namespace emthrm
#line 11 "include/emthrm/graph/matrix_tree_theorem.hpp"
namespace emthrm {
template < typename T , typename CostType >
T matrix_tree_theorem ( const std :: vector < std :: vector < Edge < CostType >>>& graph ,
const T eps = 1e-8 ) {
const int n = graph . size ();
if ( n == 1 ) [[ unlikely ]] return 1 ;
Matrix < int > laplacian ( n , n , 0 );
for ( int i = 0 ; i < n ; ++ i ) {
for ( const Edge < CostType >& e : graph [ i ]) {
++ laplacian [ e . src ][ e . src ];
-- laplacian [ e . src ][ e . dst ];
}
}
Matrix < int > cofactor ( n - 1 , n - 1 );
for ( int i = 0 ; i < n - 1 ; ++ i ) {
std :: copy ( std :: next ( laplacian [ i + 1 ]. begin ()), laplacian [ i + 1 ]. end (),
cofactor [ i ]. begin ());
}
return det ( cofactor , eps );
}
} // namespace emthrm
Back to top page