Dotcpp  >  编程教程  >  图论  >  简述矩阵树定理

简述矩阵树定理

点击打开在线编译器,边学边练

Kirchhoff矩阵树定理可以简称矩阵树定理,可以解决了一张图的生成树个数计数问题。

本篇中的图,无论无向还是有向,都允许重边,但是不允许自环。


一、概况

1. 无向图情况

设G是一个有 n 个顶点的无向图。定义度数矩阵 D(G) 为:

01.png

矩阵树定理为点 i 与点 j 相连的边数,并定义邻接矩阵A为:

邻接矩阵

定义 Laplace 矩阵(亦称 Kirchhoff 矩阵)L为:

Laplace 矩阵

记图G的所有生成树个数为t(G)。


2. 有向图情况

设G是一个有 n 个顶点的有向图。定义出度矩阵出度矩阵为:

出度矩阵

类似地定义入度矩阵出度矩阵


邻接矩阵为点 i 指向点 j 的有向边数,并定义邻接矩阵A为:

邻接矩阵

定义出度 Laplace 矩阵出度为:

出度 Laplace

定义入度 Laplace 矩阵入度 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)是

BEST 定理

 注意,对欧拉图G的任意两个节点节点,都有节点,且欧拉图G的所有节点的入度和出度相等。



知识点标签:


本文固定URL:https://www.dotcpp.com/course/1058

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)