Matrix-Tree 定理

Kirchhoff矩阵

$D[N][N]$ 为图的度数矩阵,$D[i][i]$为点i的度数,其余元素为0
$G[N][N]$ 为图的邻接矩阵,$G[i][j]$为i,j间的边数

基尔霍夫矩阵 $K = D - G$

生成树计数

  • 有向图度数矩阵为每个点的入度
  • 自环不计入度数矩阵
  • 外向树:所有边指向子节点的生成树
  • 无向图生成树个数 = |K的任意一个n-1阶主子式|
  • 有向图外向树个数 = |K的去掉根所在阶的n-1阶主子式|
  • | | 表示行列式的值,即高斯消元后主对角线的乘积
  • 一个n-1阶主子式子即去掉第r行第r列的行列式

BEST 定理

有向图的欧拉回路个数
$ec(G) = t_s(G)deg(s)!\prod_{v \in V,v \neq s}(deg(v) -1)!$

$t_s(G)$ 表示以s为根的外向树个数

Cayley公式

  • 完全图有$n^{n-2}$棵生成树,即n个节点带标号的无根树
  • 任何一个长为n-2,取值范围在1到n之间的Prüfer数列都唯一地对应了一棵n个节点的无根树
  • n个节点的度数分别为$d_1,d_2,\dots,d_n$的无根树共有$\frac{(n-2)!}{\prod (d_i-1)!}$棵

题目

csu1805

三个点A B G
AB 间有 a条,AG间有 b条,BG间有 c条双向道路
求从A出发又回到A,经过所有边的回路(即欧拉回路)个数

枚举a条边的入边,然后计算出点的入边/出边,应用BEST定理

2016四川省赛H

参考