为什么把边换成路径?
欧拉(Euler)公式给出的边数界能迅速证明一些图非平面,但稀疏图可能通过这些检验。例如,把 的每条边都换成两条边组成的路径,原来的连接关系仍在,新增的九个顶点却令边数界宽松得多。要把这个直觉变成证明,必须准确说明哪些路径替代了哪些边,以及插入或消去路径内部顶点为何保持平面性。
本节的图均为有限简单无向图。
定义 3.2.1
(细分与分支顶点)
图 的一个细分是把每条边 换成一条正长度的 – 路径所得的图;这些替代路径的内部顶点两两不相交,且都不是 的原有顶点。长度为一表示该边不变。原有顶点称为分支顶点。每条替代路径的内部顶点在细分图中度数为二;若细分图处于一个更大的图中,这些顶点在大图中可以有额外的边。
定理 3.2.2
(细分保持平面性)
有限简单图 平面,当且仅当它的任意细分 平面。
证明
(在弧上标点与连接弧)
若已有 的平面嵌入,就在每条边弧的内部标出所需数目的不同点作为新顶点;所得的 仍没有交叉。
反过来,设 已有平面嵌入。对每条替代路径,把其连续的边弧合看为连接两个分支顶点的一条弧,并不再把内部点视为顶点。路径没有重复顶点,所以这条拼接弧是简单弧。不同替代路径内部顶点互不相交,嵌入中的边也没有交叉,因此这些弧只可能在共同的分支端点相遇。所得图形恰好是 的平面嵌入。未细分的边和孤立顶点也没有问题。
证明透视
反方向为何成立
正方向只是在弧上标点。反方向才用到细分的定义,而定义的每一项各有作用。替代路径没有重复顶点,使连接起来的弧是简单弧,而不是与自身相交的曲线。内部顶点两两不相交,加上 的嵌入没有交叉,使两条连接弧只在共同分支顶点处相遇。内部顶点都不是 的原有顶点,则防止一条弧穿过分支顶点。若去掉内部不相交的条件,论证就在第二项失效:在下面反例的星图中,九条路径都经过同一个顶点,它们连接后的弧会在那里相遇。
推论 3.2.3
(非平面性的细分证据)
若图 含有一个子图,它是某个非平面图 的细分,则 非平面。
证明
(把嵌入限制到子图)
由定理,细分 非平面。若 有平面嵌入,删去 之外的顶点和边便得到 的平面嵌入,矛盾。
实际写出证据时分两步。先指定子图 :列出分支顶点,对 的每条边给出一条对应路径。再核对不同路径没有共同内部顶点、路径内部也没有分支顶点。大图里的额外边可以不选入证据;子图不必是诱导子图。
仅指出若干顶点之间都有路径并不够:必须列出路径并检查互不相交的条件。另一方面,两所选顶点之间的额外边只要不选入子图,就不影响证据。
消去度为二的顶点到底做了什么?
逆向证明并不要求移动曲线。细分图嵌入中的每条边都是弧;替代路径的相邻边弧只在共同端点相接。因此,它们的并是一条弧,中间的度二顶点现在只作为弧上的普通点。这称为消去这些顶点。由于没有其他所选边经过内部顶点,不会产生新的交点。若该点在大图中还接有额外边,应先舍去这些边:消去操作作用于所选子图,不一定作用于整个大图。
反过来看,沿一条边插入一个顶点, 和 各增加一。因此 减少二, 减少一。反复细分会让这些必要的边数界更容易满足,却不改变平面性。使用二部图的界之前必须另行核对二部性:只细分一条边可能破坏它,例如四边形会变成五边形。若每条边都细分一次,原顶点和新顶点分别构成两部,所得图一定是二部图。
细分与图子式
定义 3.2.4
(图子式)
图的子式(minor)可通过删除顶点、删除边及收缩边得到;回到简单图时删除自环并合并重边。
每个 的细分都以 为子式:在每条替代路径上收缩除一条以外的所有边,但不把两个分支顶点合并。内部不相交保证各条路径可独立处理。反过来不成立:取相邻的两个三度顶点,各自再接两个叶子。收缩连接这两个顶点的边,得到 。但原树的最大度为三,不可能含有 的细分,因为后者的中心对应顶点须接出四条不同路径的首边。因此子式证据与细分证据的核查要求不同。
一个稀疏障碍
例题 3.2.5
(细分 的每一条边)
设 的两部为 和 。对每个跨部顶点对 ,引入不同的新顶点 ,用 替换边 。所得图 有 个顶点和 条边。六个原顶点是分支顶点,九条路径的内部顶点各不相同;所以 是非平面的 的细分,也非平面。
普通平面图边数界允许 ;二部平面图的更强界也允许 。事实上, 是二部图:一部取六个原顶点,另一部取九个新顶点。这两个不等式都未检测出障碍。再加入只与 相邻的新叶子 和额外边 ,所得大图仍非平面:删去叶子与额外边后,证据 仍在。
反例模式
共用内部顶点的路径不够
取六个顶点 和第七个顶点 ,只把 分别连到其余六点。每个跨部顶点对都有一条如 的路径,但九条所提路径都共用内部顶点 ,并不构成 的细分。实际上此图是一棵星形树,完全可以平面嵌入。若不检查内部不相交,路径存在性不能证明非平面。
写出两份可核对的证据
例题 3.2.6
(额外边中隐藏的 细分)
取分支顶点 ,加入路径 和 ,其中 为互不相同的新顶点。其余八个分支顶点对直接用边 相连。再加入边 。这十条所需路径中,两条的内部顶点集分别是 、,其余八条没有内部顶点,因此符合细分条件。选取证据子图时舍去 。所选子图是 的细分,故整个图非平面。大图共有八个顶点:五个分支顶点和三个内部顶点;列出的十条路径证明任何画法都不能成为平面嵌入。
例题 3.2.7
(路径长度不等的 证据)
取两组分支顶点 和 ,使用以下九条路径:
设 为六个不同顶点,且都不在分支顶点中。还可加入边 。九条路径恰好对应九个跨部顶点对,其非空内部顶点集为 、、、 和 ,两两不相交。所选子图不包含额外边 ,所以即使大图中两个内部顶点还有额外边,它仍是 的细分证据。所选子图有十二个顶点和十五条边;普通平面边数界允许 ,仅凭这个计数无法断定平面性。
实际寻找证据时,可以先找度数足够的候选分支顶点,再追踪连接路径。画图时消去看似度二的链可以提示基本图,但最后仍应列出路径。尤其是,度数本身不能证明细分存在;大图中的分支顶点也可以有额外邻点。
旁注
在稀疏图中先试二部障碍
细分需要五个度至少为四的分支顶点,而 细分只需要六个度至少为三的分支顶点。若度为四的顶点很少,应先找 。
证据能说明什么
和 的非平面性可由欧拉公式的边数界证明。以上论证给出一个方向:含有其中任一图的细分的图必非平面。它本身并未证明每个非平面图都含有这样的细分;后者是更深的 Kuratowski 定理,本节不证明。找不到证据不等于找到了平面嵌入,通过边数检验也不等于平面。要证明平面性,可以给出无交叉嵌入或其他有效论证。
细分是沿边插入度为二的顶点,与在大图中任意收缩一条边不同。图形可以帮助发现证据,最终仍应写出可核对的路径。
常见错误
(度数本身不能证明细分存在)
高度数只能提示候选分支顶点,并不能证明什么。八面体图可画成三角形 围住三角形 ,其中 连到 , 连到 , 连到 ;这个画法说明它是平面图,但它的六个顶点度数都是四。任取五个顶点都通过 分支顶点的度数检验,然而平面图不可能含有 的细分。
常见错误
(通过边数检验不等于平面)
有 个顶点、 条边的细分 同时满足 与 ,却非平面。边数界只是必要条件;要证明平面性,应给出嵌入。
练习
快速检查
(将 的一条边细分一次。计算顶点数和边数,检查普通平面边数界,并证明所得图非平面。)
解答 · 答案
顶点有六个,边有十一条:删去一条边再添两条,边数由十增至十一。边数界允许 。但消去新增的度二顶点便恢复 ,由细分保持平面性可知所得图非平面。
快速检查
(一个图含有 的细分,又在不同替代路径的两个内部顶点之间加了一条边。为什么额外边不破坏证据?)
解答 · 答案
选取原来的细分路径,不把额外边选入子图。所选路径的内部顶点仍两两不相交,故所选子图仍是 的细分;这些顶点在大图中的度数并不妨碍此证明。
快速检查
(从两部为 和 的 删去边 。描述一个平面画法,并说明为什么这不与 非平面矛盾。)
解答 · 答案
画出三条内部不相交的路径 、 和 ,形成平面上的三个弧形区域。在第一、二条路径之间的一个面中放入 ,在该面内分别连到 和 ,不产生交叉。这恰是 。删除边可能使非平面图变为平面图;非平面性从子图传给超图,不能反向推。
快速检查
(有人声称把平面图的一条边细分一次可能产生非平面图。指出错误并解释正确结论。)
解答 · 答案
在原平面嵌入的一条边弧内部标出新顶点,即得所需细分,且不会产生交叉。因此细分后的图仍平面。另一个有交叉的画法不能否定这个无交叉嵌入的存在。
快速检查
(构造一个以 为子式、却不含 细分的图,并证明这两点。)
解答 · 答案
将两个三度顶点相连,各自再接两个不同的叶子。收缩中间边得到一个中心连着四个叶子的 。原图最大度为三,而任何 细分的中心必须接出四条不同路径的首边,所以原图不含这样的细分。