动机
知道一个连通图有生成树,并不能告诉我们有多少种选择。直接搜索所有边子集,即使每个候选都容易检验,代价也会变得很高。关联矩阵把这个问题转化为一个行列式,其中的抵消作用会自动剔除含圈的选择。
权重所保留的信息比单个计数更多。边权的乘积记录了每一棵树,它们的和则成为一个生成多项式。对该多项式求导,就能回答关于随机选取一棵加权树的概率问题。
行列式恒等式在此处给出证明;只假设有限维矩阵乘法以及行列式的多重线性。
定义
定义 1.6.1
(带标号的边、关联与生成树多项式)
设 是有 个顶点的有限无向多重图,其边带有标号;允许存在自环与平行边。给每条边赋予权重 ,起初它是有理数域上的不定元。生成树包含每个顶点,是连通的且不含圈;自环永远不属于生成树,两条平行边构成长度为二的圈。
定义
对于只有一个顶点的情形,即使存在自环,空树也贡献一。顶点数多于一的非连通图,其生成树多项式为零。
对每条非自环边任意指定方向。其关联列在起点处为负一,在终点处为正一,其余位置为零。自环对应零列。设由此得到的 行 列矩阵为 ,边权的对角矩阵为 。加权拉普拉斯(Laplace)矩阵为 。其非对角元等于这两个顶点之间各边权之和的相反数;其对角元是与该顶点关联的非自环边的权之和。这一约定同样将自环排除在对角线之外。
选定根顶点 ,从 中删去它所在的行,得到 。从 中删去根所在的行与列,得到 。零阶矩阵的行列式规定为一。
定理/命题
定理 1.6.2
(拉普拉斯矩阵的每个主余因子都等于生成树多项式)
对每个有限加权多重图以及任意选定的根,
该等式是多项式恒等式。特别地,取单位权重时,它恰好给出带标号生成树的数目,并且该行列式既不依赖于任意指定的边方向,也不依赖于删去哪个根。
定理 1.6.3
(完全图与完全二部图有显式的计数公式)
对于 个顶点的简单完全图,其生成树数目为 。单顶点的情形计数为一。对于两部分大小为正整数 的完全二部图,其计数为
该公式包括星图和单边图;两部分的大小均为正,是命题陈述的一部分。
定理 1.6.4
(正的加权树分布具有精确的边边缘概率)
设 连通,且所有非自环边的权重均为正实数。以与权重乘积成正比的概率选取一棵生成树。设 为边 的约化关联列, 为约化拉普拉斯矩阵。则
对于自环,右端为零。这些边缘概率之和为 ,且每一个都介于零与一之间。改变边的方向不影响它们。
概念视角代数
一个多项式同时支持计数、灵敏度分析与随机选取
单位权重用来计数,形式权重保留了哪些边出现,正的数值权重则定义出一个概率分布。行列式恒等式是这三种用法所共有的,但只有在后面的正性与连通性假设下,才会用到可逆性与概率意义下的除法。
下面的证明按这个次序进行:先证余因子恒等式,再算两个显式图族,最后处理概率分布。
证明思路或证明
行列式展开挑出了树的边集
论证建立在一个长方形行列式展开之上。
引理 1.6.5
(柯西–比内(Cauchy–Binet)展开)
设 是 矩阵, 是 矩阵,则
其中 取遍 的 元子集;当 时和为空。
证明
(以列的多重线性证明)
设 是 行 列的矩阵, 是 行 列的矩阵,则由列的多重线性, 可按从 中有序选取 列的方式展开。含有重复下标的选取,其行列式为零。对于固定的由 个互不相同的下标构成的无序集合 ,由行列式的带符号置换公式,对它们所有排列求和恰好等于 。因此
若 ,则没有互不相同的选取,和为零。当 时恰有空选取一种,两边均为一。这就直接证明了所需的柯西–比内恒等式。
证明
(主余因子公式的证明)
将柯西–比内展开应用于 与 。对每个由 条带标号的边构成的集合 ,把所选的对角因子从行列式中提出,得到
下面证明:该行列式的平方恰好在 为生成树时等于一,否则等于零。
若 含有自环,则其关联列为零。若它含有圈,则沿该圈绕行,并按绕行方向选取符号,把该圈上各边带方向的关联列相加,每个顶点的贡献都相互抵消,从而得到一个非平凡的线性相关关系。这也包括带有适当符号的两条平行边。删去一行关联矩阵后该相关关系仍然保持,所以所选子矩阵的行列式为零。
若 无圈,则它是森林。一个有 个顶点、 个连通分支的森林有 条边,这可由对各分支(包括孤立顶点)内的树的边数求和得到。这里 迫使 ,所以它是生成树。
对于树,我们对 用归纳法证明行列式的绝对值为一。 的情形是空行列式。对于 ,树有一个不同于所选根的叶子:取一条最长路径的两个端点,其中至少有一个不是该根。该叶子的约化关联行恰有一个非零元,等于正一或负一。沿该行展开,行列式在相差一个符号的意义下化为去掉该叶子及其边之后的树的约化关联行列式。再由归纳法即完成论证。代入这些取值为零或一的系数,公式即得证。
证明透视
行列式是在挑选关联约束的基
三个要素各有分工。柯西–比内展开把 化为对所有 边集合的求和,每项带权 ;正因为子式取平方,定向的符号永远无关紧要。圈的论证负责剔除非树:圈给出关联列之间带符号的线性相关,删去根所在的行后仍然成立,所以含圈或含自环的集合贡献为零。森林计数保证大小为 的无圈集合连通,因此留下的只有生成树。
随后,叶子的展开把每个保留下来的系数固定为一,使论证收尾。这里删去根行是关键:树的完整关联矩阵是 的,并非方阵;而 时总有一个不同于根的叶子。若不删去根, 是奇异矩阵,常见错误中的反例正说明这一点。
不枚举树而计算两个重要的图族
两个显式图族还需要一个行列式事实。
引理 1.6.6
(秩一行列式更新)
对于可逆方阵 与列向量 ,
证明
(展开扰动单位矩阵的证明)
为证明它,先提出因子 ,再按列的多重线性展开 。在两列中都选取所加向量的项为零,因为这两列成比例。一列都不选的项为一;只在一列中选取的项之和为 。这就证明了该事实,按空向量的自然约定,阶数为零的情形也包括在内。
证明
(两个显式计数的证明)
对于 ,约化拉普拉斯矩阵为 阶的 ,其中 的每个元素都是一。由秩一恒等式,其行列式为 。该论证在 时同样成立;单顶点的情形已另行定义过。
对于 ,在大小为 的那一部分中删去一个根。对角块为 与 ,非对角块是元素全为负一的矩阵。用第一个块的行的适当倍数去消去左下角的块;这些行加法不改变行列式。下方的对角块变为
其行列式为 。再乘以 ,即得所述结果。当 时,第二个块为空,同一表达式的值为一;这里并不需要对大小为空的正的那一部分求逆。
正权重把多项式变为概率分布
证明
(边缘概率公式的证明)
对于约化向量 ,在其根坐标处插入零,得到完整向量 。则
在非自环边权重为正时,只有当 沿每条边都取常值,这个量才为零。连通性与根处坐标为零迫使 。因此对于 , 是正定的,从而可逆;单顶点的空矩阵按通常约定有空逆矩阵。
生成树多项式对每个单独的权重都是线性的。因此 是包含 的所有树的权重之和。在矩阵一侧,仅将 改变 ,会使 改变 。由秩一行列式公式,其导数为 。把这两个相等的导数除以正的归一化多项式,就得到边缘概率公式。
每棵树恰有 条边,所以把各边的边缘示性量相加,即得所断言的和,而无需假设边之间相互独立。自环的关联列为零,从不进入任何树;把一条边反向会使它的列在两处同时变号,结果不变。
区分算法计算与恒等式
构造拉普拉斯矩阵需要对边做线性次数的累加,在稠密实现中需要二次的矩阵存储。行列式可以用消元法以三次的算术运算量求出,需要时选取非零的行主元。在权重为正时,约化矩阵是正定的,所以精确消元的对角主元非零。这些是关于算术运算次数的陈述;任意有理数输入的长度以及精确分数的增长需要另行做比特计量,浮点计算的可靠性则需要进一步分析。
该公式还给出了一个直接的多项式恒等式,无需数值行列式算法也有用。对于一条非自环边,把树分成不含它的和含有它的两类。收缩这条带标号的边,给出后一类与收缩后的多重图的生成树之间的双射,其余所选的边保持不变。因此 。收缩可能产生自环与平行边,它们仍沿用前面已述的约定。自环则直接忽略。
例题详解
例题 1.6.7
(加权三角形记录了全部三种删除方式)
给三角形的三条边赋予权重 。其生成树多项式为 。删去边 所共有的那个顶点,得到约化矩阵,其对角元为 ,非对角元为 。其行列式为 。
在单位权重下有三棵树,每条边的包含概率都是三分之二。在权重 时,归一化常数为五,权重为二的那条边出现的概率为五分之四。较大的权重改变的是分布,而不是产生了四个互不相同的带标号副本。
例题 1.6.8
(平行边的选择相乘,而自环没有贡献)
取顶点 ,在 之间有权重分别为二和三的两条平行边,在 之间有一条权重为五的边。在 处再加一个任意权重的自环。每棵树都使用通向 的桥,并恰好使用两条平行边中的一条,所以其多项式的值为 。
以 为根,得到对角的约化矩阵,其元素为五和五。桥的边缘概率为一;两条平行边的边缘概率分别为五分之二和五分之三;自环的边缘概率为零。它们的和为二,恰好等于每棵生成树的边数。
例题 1.6.9
(两个图族给出不同量级的计数)
五个顶点的完全图有 棵生成树。两部分大小分别为二和三的完全二部图有 棵。
对于后者,以大小为三的那部分中的顶点为根,得到对角块 以及元素全为负一的非对角块。消元后下方的块为 ,其行列式为 ;第一个块贡献九,从而得到十二。这个小计算展示了分块消元的过程,而不只是引用封闭公式。
常见错误
反例模式
即使图是连通的,完整拉普拉斯矩阵的行列式也为零
每个关联列的元素之和为零,所以全一向量属于完整拉普拉斯矩阵的核。对于单边图,拉普拉斯矩阵的对角元为一,非对角元为负一;其行列式为零,尽管恰有一棵生成树。删去一个根所在的行与列,得到元素为一的一阶矩阵,这才是所需的余因子。
常见错误
(把自环的权重放到对角线上)
自环的关联列为零,所以它对 没有贡献,也从不属于生成树。若把它的权重加到对角元上,余因子就会改变:在以 为根的平行边例子中,若在 放一个权重为 的自环并计入对角线,行列式会由 变为 ,而生成树并没有改变。
常见错误
(合并带标号的平行边)
平行边是不同的带标号边,给出不同的生成树。在平行边例子中,把权重为 与 的两条边换成一条权重为 的边,会得到 而不是 。只有合并后的边带有总权重 ,生成计数才保持不变;即使如此,两条边各自的边缘概率 与 也会丢失。
常见错误
(把边缘概率当作独立包含)
边缘概率之和为 ,但树的边一般是相依的。在单位权重的四圈中,每条边的概率都是 ,四条边却从不同时出现;若各边独立包含,四条边同时出现的概率将是正数 。逆矩阵公式也需要图连通:若 不连通且 ,则 , 奇异,根本没有可归一化的分布。
总结
关联矩阵的子式把拉普拉斯矩阵的一个余因子变成完整的加权生成树多项式。含圈的项消失,树对应的子式的行列式绝对值为一。秩一与分块消元给出了完全图与完全二部图的显式计数,而正权重则给出精确的边边缘概率,并清楚地区分了多项式恒等式与基于逆矩阵的概率计算。
练习
快速检查
(求四圈的生成树数目,以及在单位权重下每条边的包含概率。检验边缘概率之和。)
每棵树恰好省去圈上的一条边。
解答 · 答案
删去四条圈边中的任意一条,都剩下一条生成路径,所以共有四棵树。每条指定的边被其中一棵树省去,被其余三棵树包含,边缘概率为 。这四个边缘概率之和为三,等于四个顶点时的 。这些边并不独立:它们同时被包含是不可能的,因为整个圈不是树。
快速检查
(对单位权重三角形的一条边应用删除–收缩。解释为什么收缩后的图有两条带标号的平行边,以及它们的数目如何贡献到计数中。)
收缩之后要保留多重图中边的身份。
解答
删去所选的三角形的边,剩下一条生成路径,贡献一。收缩它则得到由两条不同的带标号平行边连接的两个顶点。其中任意一条单边都是该多重图的生成树,贡献二。因此删除–收缩给出 。
若把这些平行边合并成一条不带权的边,则总共会错误地得到二。若把它们合并成一条权重为二的边,则就此目的而言可以保持生成计数,但需要理解这会丢失各自独立的边缘概率身份。
快速检查
(计算 的生成树数目,以及四个顶点的完全图的生成树数目。解释为什么第一个图的边缘概率全为一。)
星图只有一棵可能的生成树。
解答 · 答案
二部图公式给出 。星图的七条边中每一条都是桥,都属于那唯一的树,所以七个边缘概率都等于一,和为七。对于四个顶点的完全图,公式给出 。它多出的圈带来了更多选择;这两个公式是在不同的外围图中数树,而不只是使用了相同的顶点数。