Kirchhoff矩阵树定理可以简称矩阵树定理,可以解决了一张图的生成树个数计数问题。
本篇中的图,无论无向还是有向,都允许重边,但是不允许自环。
一、概况
1. 无向图情况
设G是一个有 n 个顶点的无向图。定义度数矩阵 D(G) 为:
设为点 i 与点 j 相连的边数,并定义邻接矩阵A为:
定义 Laplace 矩阵(亦称 Kirchhoff 矩阵)L为:
记图G的所有生成树个数为t(G)。
2. 有向图情况
设G是一个有 n 个顶点的有向图。定义出度矩阵为:
类似地定义入度矩阵
设为点 i 指向点 j 的有向边数,并定义邻接矩阵A为:
定义出度 Laplace 矩阵为:
定义入度 Laplace 矩阵为:
记图G的以 r 为根的所有根向树形图个数为 。所谓根向树形图,是说这张图的基图是一棵树,所有的边全部指向父亲。
记图G的以 r 为根的所有叶向树形图个数为。所谓叶向树形图,是说这张图的基图是一棵树,所有的边全部指向儿子。
二、定理叙述
矩阵树定理具有多种形式。其中用得较多的是定理 1、定理 3 与定理 4。
定理 1(矩阵树定理,无向图行列式形式) 对于任意的 i,都有
其中记号表示矩阵L(G)的第行与第列构成的子矩阵。也就是说,无向图的 Laplace 矩阵具有这样的性质,它的所有 n-1 阶主子式都相等。
定理 2(矩阵树定理,无向图特征值形式) 设为L(G)的 n-1 个非零特征值,那么有
定理 3(矩阵树定理,有向图根向形式) 对于任意的 k,都有
因此如果要统计一张图所有的根向树形图,只要枚举所有的根 k 并对求和即可。
定理 4(矩阵树定理,有向图叶向形式) 对于任意的 k,都有
因此如果要统计一张图所有的叶向树形图,只要枚举所有的根 k 并对求和即可。
BEST 定理
定理 5 (BEST 定理) 设G是有向欧拉图,那么G的不同欧拉回路总数ec(G)是
注意,对欧拉图G的任意两个节点,都有,且欧拉图G的所有节点的入度和出度相等。
知识点标签:树
本文固定URL:https://www.dotcpp.com/course/1058