把相互冲突的顶点分成两类
假设每个顶点要涂上两种颜色之一,而且每条边的两端颜色不同;例如这可表示把相互冲突的任务分成两组。
定义 1.2.1
(二部图)
存在这种染色的图称为二部图:两个颜色类构成顶点的划分,其中一类可以为空。
以下考虑有限无向简单图,允许不连通及孤立顶点。圈至少有三个不同顶点,起点在结尾重复除外。
奇圈判据
定理 1.2.2
(二部图等价于没有奇圈)
有限无向简单图是二部图,当且仅当它不含奇数长度的圈。
证明
(颜色交替与树距离的奇偶)
若存在合法二色染色,沿每条边行走都会转换颜色。沿圈回到起点颜色必须转换偶数次,因此每个圈长度均为偶数。
反过来,在每个连通分支分别处理。选一个根并建立广度优先搜索树,按顶点到根的树距离奇偶染色。假设某边 两端同色。由 到 的唯一树路径长度为偶数:若 是它们的最低共同祖先,其长度为 。边 不是树边,因为树边两端的深度奇偶不同。把它加到简单树路径上得到奇圈。因此若没有奇圈,没有边可连接同色顶点,染色必定合法。孤立根可取任一颜色。
证明透视
失败的边如何给出具体见证
两条由根通往顶点的路径可能共用开头部分,因此直接把两条完整路径和该边接起来可能重复顶点。移去共同部分,改用经最低共同祖先的唯一树路径。它是简单路径;端点奇偶相同时,其长度为偶数,加上非树边便形成奇圈。这同时说明证书的奇偶性和简单性。
算法及输出
从未染色顶点开始广度优先搜索,给它颜色零,并让每个新发现邻点取相反颜色。若检查到某边的两端同色,利用两条树路径及该边重构并输出奇圈。若一个分支无冲突地结束,就从另一未染色顶点重新开始;全部完成后输出两个颜色类。用邻接表时,每个顶点和每条边只检查常数次,时间为 ,包括输入表示的空间为 ;重构一个见证所需的父节点指针只用额外 空间。空图输出两个空类。
例子
例题 1.2.3
(路径与四圈)
对路径 ,以 为根,深度奇偶给出颜色类 和 ,每条边都跨越两类。加入 得到四圈,此染色仍然有效。
例题 1.2.4
(三角形给出最短的见证)
对三角形边 ,以 为根。广度优先搜索可令 都是 的子节点,因此同色。边 产生冲突;树路径 加上 是长度三的奇圈。另一个孤立顶点可取任一颜色,但不会消除此障碍。
例题 1.2.5
(五圈:冲突边远离根)
取圈 ,以 为根进行搜索。则 的深度为 , 的深度为 ,父节点分别是 和 。边 连接两个深度为 的顶点,所以它就是冲突边。两者的最低共同祖先是 ,树路径长度为 ,即 。加上 ,见证就是整个五圈。这里见证和三角形的情形一样经过根;一般而言最低共同祖先可以更深,只用到两条根路径在它之下的部分。
反例模式
只检查一个分支不够
一个图可以有二分的分支,另有独立三角形。若只从第一个分支开始搜索,就找不到冲突,但整个图不是二部图。从每个未染色分支重新开始是算法的一部分,不是外观细节。
常见错误
(一个偶圈什么也证明不了)
找到一个偶圈并不能说明图是二部图。 含有四圈 ,但 是三角形。判据要求没有任何奇圈,实际上要用整个图的合法二色染色来证明。
常见错误
(自由选色造成的冲突不是见证)
逐个顶点任意选色,即使在二部图中也可能出现冲突。在路径 上,先取 、,此时两者尚无联系;接着 是被迫的,而 必须同时异于 和 ,这不可能。但这条路径是二部图。只有当涉及的每个颜色都是从同一分支的一个根被迫推出时(例如广度优先搜索),冲突才证明奇圈存在。
练习
快速检查
(给六圈 一个二色染色。)
解答 · 答案
取 和 。
快速检查
(解释为什么在二部图中加入连接两个同色顶点的弦会破坏该染色;每条新边都会破坏二分性吗?)
解答 · 答案
新边的两端同色,违反该染色;但不是所有新边都破坏二分性,例如加入一条原本不存在、跨越两类的边可保留它。
快速检查
(广度优先树的根 有子节点 ,图另有边 。给出奇圈见证。)
解答 · 答案
树路径 加上 是三边圈。
快速检查
(对三个孤立顶点,算法可输出什么?)
解答 · 答案
三个顶点的任意划分都是合法二色染色;每次由新顶点重启,可把三者全放在一类,另一类留空。