动机
生成树以无冗余的边连接所有顶点。加一条边会产生一个圈;加多条边则会产生许多互相重叠的圈。怎样不逐一枚举所有圈,就描述每个偶度边集?方法是为每条非树边保留一个基本圈,用对称差组合它们。这为后续割与平面对偶论证中使用的循环空间提供了具体的基。
定义
本节 是有限无向简单图,有 个顶点、 条边和 个连通分支,孤立顶点也算分支。
定义 1.3.1
(边集与偶度边集)
边集指 的子集,同时保留原来所有顶点;某顶点在该边集中的度数只计算选中的关联边。若每个顶点的选中度数均为偶数(包括零),称该边集为偶度边集。空边集是偶度的。
定义 1.3.2
(对称差与循环空间)
边集 的对称差 是恰好属于 之一的边所成的集合。将每个边集视为 中的零一向量,对称差就是加法。 的循环空间是所有偶度边集连同这个加法所成的集合。
每个顶点在 中的度数奇偶性,等于它在 中度数奇偶性的模二和,因此偶度边集的对称差仍为偶度,循环空间是 的子空间。空间的元素是边集,不一定是单个简单圈。
定义 1.3.3
(生成森林与基本圈)
的生成森林 是一个无圈边集,在每个连通分支内包含一棵生成树。对不在 中的边 , 中唯一的 – 路径与 组成基本圈 。
生成森林满足 ,包括孤立顶点及空图的情形。每条不在 中的边 的端点处于同一分支,所以 中存在 – 路径;又因 无圈,这条路径唯一。 唯一不在森林中的边就是 。
定理 1.3.4
(基本圈构成基)
对任意生成森林 ,每个偶度边集 都有唯一表达式
空对称差为空集。因此基本圈构成循环空间的基,其维数为 ,空间恰有 个边集。
证明
(消去非森林边的证明)
设 为偶度边集,令
每个 恰有一条非森林边,即 本身。因此除 本身外, 中每条非森林边 恰出现在所加的一个集合中,从而被抵消;不在 中的非森林边则不出现在任何一个集合中。所以 。每个基本圈都是偶度边集,对称差保持偶度,所以 仍为偶度。
森林内的偶度边集只能为空。否则其选中子图是非空森林;其中某个含边的分支是非平凡树,有选中度数为一的叶顶点,与偶度矛盾。因此 ,即得 的上述表达式。
唯一性:设 ,其中 是某个非森林边集合。在所有基本圈中,非森林边 只出现在 中,所以 当且仅当 ,故 。特别地,基本圈线性无关,而第一部分说明它们张成空间。它们有 个,这个基的 个子集给出不同的偶度边集。
证明透视
无圈与生成各用在哪里
证明分开使用 的两个性质。“生成”只用来保证每条非森林边都有基本圈:它的端点在同一分支内,而 连通该分支。“无圈”用了两次:使路径从而 唯一,以及通过叶顶点论证说明 内的偶度边集为空。
关键一步是观察到每个 与非森林边的交恰为 。以非森林边为坐标,基本圈就是标准单位向量。这一个事实既清除了 的非森林部分,又读出了系数,所以存在性与唯一性来自同一观察。论证之所以收尾,是因为剩下的是一个没有余地保持非空的偶度边集。
每个假设都不可缺。在三角形中取 ,它无圈但不生成,没有任何边有基本圈,三角形却是偶度的。若 取整个三角形,它生成但不无圈,就没有非森林边,表达式只给出 ,三角形同样被遗漏。
森林本身没有非森林边,其唯一偶度边集为空。非连通图中每个基本圈都留在自己的分支内,不需要虚构连接不同分支的边。更换生成森林会改变所选的基,却不会改变偶度边集本身或它们的数目。
概念视角代数
循环空间是一个核
设 是 在 上的 顶点–边关联矩阵。对指示向量为 的边集, 就是 的选中度数模二。所以循环空间恰为 。由秩–零化度定理,,于是基定理同时算出秩:在 上 。 中以 为指标的行就是割 ,对顶点集 中的行求和得 ,所以 的行空间正是下面研究的割的集合。
核的描述把偶度化为一个线性方程;下一节研究行空间,即割。
圈、割与奇偶
定理 1.3.5
(偶度边集可分解成圈,且与割偶数相交)
每个非空偶度边集都可写成边互不相交的简单圈之并。对任意顶点集 ,偶度边集与割 的交集有偶数条边。
证明
(剥去圈与对度数求和的证明)
先证第一项。只看选中边及其关联顶点组成的子图;其中每个顶点的正度数都是偶数,至少为二。在这个子图中取最长简单路径。由极大性,其末端顶点的所有邻点都在路径上,而末端顶点有一个不同于相邻前驱的邻点;这条边闭合成一个简单圈。删除该圈的边:每个圈上顶点恰失去两条选中关联边,因此剩余边集仍为偶度。不断重复,每次都删除边,最终结束。得到的圈边互不相交,但可以共用顶点,分解也未必唯一。
再对 中顶点求选中度数之和。 内部的每条选中边贡献二,穿过割的每条选中边贡献一。该和为偶数,故穿割的选中边数也为偶数。证明适用于任意顶点集,不要求两边诱导图连通。
特别地,桥不可能属于偶度边集:删除桥 后,含其一个端点的分支的顶点集 满足 ,与它相交一次会违反偶数性。反过来,不是桥的边位于某个圈上,故属于某个偶度边集。这是存在性陈述,不是说每个偶度边集都包含每条非桥边。
逆命题与割空间的大小
割的奇偶定理也有逆命题。若一个边集与每个割相交的边数都是偶数,对任意顶点取只含该顶点的单点集。其割恰由该顶点的所有关联边组成;相交为偶数就说明该顶点的选中度数为偶数。逐点检查可知该边集为偶度。因此检查所有单点割已足以证明偶度;前面的定理随后保证它与任意割都偶数相交。
还可以计算不同割的数目。对于顶点集 ,一条边恰跨越两个割之一,当且仅当它跨越 的割。所以 ,割在对称差下组成向量空间。空集和整个顶点集都对应空割;一般说来,不同顶点集也可能产生同一个割,不能把全部 个顶点集当作不同割来计数。
定理 1.3.6
(不同割的数目)
对顶点集 , 当且仅当 是若干完整连通分支的并。因此 恰有 个不同的割。
证明
(经由空割的证明)
由上面的恒等式, 表示 为空。一个顶点集的割为空恰表示没有边连接它与补集,于是每个分支要么全部选入,要么全部不选。这样的分支之并有 种,孤立顶点也各自提供一次选择。对任意固定割,其所有表示集恰是某个表示集与这些分支之并作对称差所得,所以每个割恰有 种表示,总数为 。空图的两个指数都为零,结论仍成立。
因此循环空间和割空间的维数之和为 。
反例模式
维数互补并不表示交集平凡
待检验的说法:既然两个维数之和为 ,循环空间与割空间就只有空边集是公共元素。取四边形 及 。边 都连接 中一个顶点与 之一,所以 就是整个四边形。同一个边集在每个顶点的选中度数都是二,所以它是偶度的。它是两个空间共有的非空边集,该说法不成立。真正成立的是 上的正交性:每个偶度边集与每个割都有偶数条公共边。这里的交有四条边,在内积中贡献零,尽管四条边都是共有的。
将该四边形与另一张仅由两个顶点及一条边组成的图比较:那条边是割却不是偶度边集,因为它的两个端点选中度数为一。整个四边形在这个图中既偶度又是割;一般图中的单个圈却未必是割。判断两个空间时要检查相应定义,不能只靠图形看起来像边界。
这个计数还说明为什么分支是表示方式中歧义的单位。连通图中将割的两侧全部互换,不改变穿割边,恰得到两种表示。多个分支之间没有边,故可以在每个分支内独立互换两侧。孤立顶点也可独立变换,却永远不会改变割边;因此不需假设割的任一侧连通。
是:在二元域上,割空间正是循环空间的正交补。
自然的下一个问题
割是否恰好是与每个偶度边集交于偶数条边的边集?
是:在二元域上,割空间正是循环空间的正交补。
每个割与每个偶度边集都交于偶数条边,因此割空间包含于循环空间的正交补。在 上这个正交补的维数是 ,与割空间的维数相同,所以两者相等。由于基本圈张成循环空间,一个边集是割,当且仅当它与每个基本圈都交于偶数条边。
例题
例题 1.3.7
(一个正方形及一条对角线)
设边为 ,选森林 。非森林边为 ,其基本圈分别为 和 。对称差抵消 ,得到 ,即另一三角形。四个偶度边集是空集、两个基本圈及其对称差。这里 。
例题 1.3.8
(分支与孤立顶点都要计算)
取顶点 上的三角形、另一条边 和孤立顶点 。则 。生成森林包含三角形的两条边及 ,故只有一个基本圈,即该三角形,而 。偶度边集只有空集和三角形。 是桥,不能被任何偶度边集选中;孤立顶点虽然没有边,却同时计入 和 。
例题 1.3.9
(圈之并未必是单个圈)
两个三角形恰共用一个顶点而不共边。它们的并为偶度边集:公共顶点度数为四,其余顶点度数均为二。该边集不是单个简单圈,因为公共顶点需要被访问两次。它仍是两个边不相交的圈之并,说明循环空间的元素不只有简单圈。
常见错误
常见错误
(普通并不是加法)
边集的普通并不是循环空间中的加法。正方形例中两个基本圈共用 ;它们的普通并是全部五条边,此时 与 的选中度数为三。对称差则抵消这两条公共边,结果为偶度。
常见错误
(维数不是圈的数目)
一组基不是全部简单圈的列表, 是独立二元选择的个数,不是简单圈的数目。正方形加一条对角线有三个简单圈,即两个三角形和正方形,但循环空间的维数是 ;正方形是两个三角形之和。
常见错误
(计算分支数时遗漏孤立顶点)
公式 只在 计入所有分支(包括孤立顶点)时成立。对一个三角形、另一条边和一个孤立顶点,若取 而保留 ,会得到 ;但三角形说明维数是 。
奇偶性要在所选边集中检查,不是在原图中检查:原图中度数为奇数的顶点,在某个偶度子集中的选中度数可以是偶数。
练习
快速检查
(正方形加对角线的例子中,用基本圈表达三角形 ,并验证各顶点的选中度数。)
使用两条非森林边 与 。
解答 · 答案
它是 。 的选中度数均为二, 为零,故它是偶度边集。
快速检查
(一个图由两个互不相交的三角形和一个孤立顶点组成。求 、循环空间维数及所有偶度边集。)
把孤立顶点算作一个分支。
解答 · 答案
,维数为 。四个偶度边集为空集、分别只取其中一个三角形,以及取两个三角形的并。孤立顶点属于图,但没有关联边。
快速检查
(证明森林中的非空边集不可能是偶度的。为什么仅数边数不足以证明?)
在选中子图中找一个叶顶点。
解答 · 答案
森林的非空选中子图有一个含边的分支,该分支是非平凡树,在选中子图中有度数为一的叶顶点,所以该边集不是偶度的。边的条数本身不能决定顶点度数:边数相同的集合可能具有不同的度数奇偶。
快速检查
(设 为任意顶点集, 为偶度边集。若 恰含 中的三条边,能得出什么结论?)
与割的奇偶定理比较。
解答 · 答案
这样的偶度边集不存在:割的奇偶定理要求选中的穿割边数为偶数,而三为奇数。这里使用的是选中边数,不是割中所有边的总数。