动机
图把连接的模式与它碰巧被画成的样子区分开来。树刻画了连通所有顶点所需的最少连接,而广度优先搜索则按到源点的距离来组织一般的图。这两个主题都体现了离散数学的一个核心方法:用局部不变量证明全局性质。
定义
定义 5.1.1
(图、路径、圈与树)
有限简单无向图 具有有限的顶点集,其边是由两个不同顶点构成的无序对,且没有重复的边。路径由互不相同的顶点组成,相邻顶点之间有边相连;其长度为边的条数。圈含有至少三个互不相同的顶点,相邻顶点之间有边相连,并有一条边回到起点。若任意两个顶点之间都有路径,则称图是连通的。树是连通且不含圈的图;森林是不含圈的图。顶点的度是与其关联的边的条数。
我们允许只有一个顶点的图作为树。在整个树的定理中,。把每条边在其两个端点处各计数一次,就得到握手恒等式 。特别地,度为奇数的顶点个数是偶数,因为把该恒等式模 约化,恰好是在计数这些顶点。
定理/命题
定理 5.1.2
(树的等价描述)
对于有 个顶点的有限简单图,下列条件等价:它是一棵树;任意两个不同顶点之间恰有一条路径;它连通且恰有 条边;它无圈且恰有 条边。
定理 5.1.3
(广度优先搜索求出无权距离)
在以邻接表表示的有限图中,从 出发,令 ,并将 放入先进先出队列。重复地取出队首顶点 ;对于 的每个尚未被发现的邻点 ,令 ,记录父结点 ,并将 加入队尾。恰好是从 可达的顶点被发现,且每个标号都等于从 出发的一条最短路径的长度。若计入对所有顶点记录的初始化,运行时间为 。
证明思路
证明
(唯一路径、叶与森林的边数)
在连通无圈图中,同一对端点之间若有两条不同的路径,则它们会包含一个圈,所以路径是唯一的。反过来,圈给出了其上两个顶点之间的两条不同路径;因此路径唯一蕴含无圈与连通。
至少有两个顶点的树有叶,即度为一的顶点。取一条最长路径:其端点若还有额外的邻点,则该邻点要么使路径可以延长,要么产生一个圈。删去该叶后剩下的仍是树。从一个顶点出发做归纳,即得恰有 条边。每个有限连通图都有生成树:只要还有圈,就删去圈上的一条边,这样连通性得以保持;该过程终止时得到一棵树。因此,有 条边的连通图已经等于它的生成树。最后,对于有 个连通分支的森林,在每个分支中应用树的边数公式,得到 。若 ,则 ,等价性证毕。
证明
(实际父路径与队列不变量)
对于 BFS,每个被发现的顶点的标号都对应一条经由父边得到的、从源点出发的实际路径,所以该标号不可能小于最短距离。队列中的标号是不减的:在处理标号为 的顶点时,新加入队列的标号为 ,排在所有已在队列中、标号为 或 的顶点之后。这一不变量在初始时成立,并且在每次取出与加入之后都保持成立。
现在考虑一条最短路径 。由归纳, 以标号 被发现。当它被处理时,由队列不变量, 要么刚被赋予标号 ,要么已经有不超过 的标号。由于最短路径的前缀仍是最短路径,其距离为 ;而由实际路径给出的上界迫使等号成立。于是每个可达顶点被发现时都带有其真实距离。不可达的顶点不可能获得父结点路径。每个顶点只进入队列一次,每条无向边被扫描两次,由此得到复杂度界。
证明透视
两个不等式,两个不同的理由
证明从两边比较每个标号与真实距离,而两个方向依赖不同的事实。不等式 只需要每个标号都由父结点的路径延长一条边而得;无论以什么顺序发现顶点都成立,包括使用栈。反方向才用到先进先出:由于队列中的标号不减,而每个新标号都比正在处理的标号大一,在处理 时已被发现的顶点,必定是由标号至多为 的顶点发现的,所以其标号至多为 。
归纳沿一条固定的最短路径进行;最短路径的前缀仍是最短路径,正是这一点使 处的归纳假设成为距离 。可达性与时间界来自同一套记录:只有可达顶点会获得父结点路径,而每个顶点只进入队列一次,所以每个邻接表只扫描一次。
例题详解
例题 5.1.4
(度数计数可以检测不可能性)
无论怎样作图,有限图都不可能恰有三个奇数度顶点。这三个奇数的贡献会使度数和为奇数,与握手恒等式矛盾。这个条件是必要的,但对于实现任意给定的度数列并不充分:在四个顶点上,度数 是不可能的,因为简单图的最大度为 。
例题 5.1.5
(仅凭边数不能确定是树)
一个三角形加上一个孤立顶点,有 且 ,但它不连通且含有圈。因此边数必须与连通性或无圈性之一同时出现。去掉三角形的一条边后得到有两个分支、两条边的森林,与 相符。
例题 5.1.6
(追踪 BFS 及其父结点的选择)
取边 。从 出发并先扫描 再扫描 ,BFS 将 标为 , 标为 , 标为 。 所记录的父结点是 。若先扫描 ,则父结点可能是 ,但距离保持不变。尽管原图含有圈 ,父边仍在可达顶点上构成一棵树。
树的每条边在结构上都是必要的
从树中删去一条边,其两个端点就不能再连通:这两个端点之间若存在另一条路径,它与被删去的边合起来就会在原来的树中构成一个圈。因此删除使图不连通。它恰好产生两个分支,因为原来的任何路径都可以在这一条边处被切开,分成位于两侧的两部分。这样的边称为桥。
反过来,圈上的边不是桥。删去后,该圈的其余部分仍然连接其端点,凡是用到这条边的路径都可以沿圈的其余部分改道。因此在连通图中,圈的存在指明了一条可以删去而不损失连通性的边。这正是不断删去圈上的边最终得到生成树的局部原因。
在树的两个不相邻顶点之间添加一条边,恰好产生一个圈。原来的树在这两个端点之间有一条路径;新边把这条路径封闭起来。由于原图无圈,扩充后的图中的任何圈都必须使用新边,去掉新边后剩下的就是原来那条唯一的路径。这同时给出了新圈的存在性与唯一性。在思考网络的逐步构建时,这一结果很有用,且不依赖任何图形的画法。
搜索森林覆盖不连通的图
从一个源点出发的 BFS 没有理由发现其他连通分支中的顶点。要探索整个图,可在当前队列变空之后,从某个尚未被发现的顶点开始新的搜索。如此重复,直到每个顶点都被发现。每次搜索为一个分支生成一棵父结点树;这些父边合起来构成一个生成森林。
因此分支数也就是搜索根的个数。没有关联边的顶点成为一棵单顶点的父结点树,仍须计入这一计数。对每个顶点初始化记录,正是所述时间界中含有顶点项的原因,即使图的边很少也是如此。一个有大量孤立顶点的图仍然需要花费工作量来逐一识别它们。
邻接表的假设解释了边这一项。每个顶点的邻点可以在与其度成正比的时间内扫描完,而各顶点的度之和等于边数的两倍。若用邻接矩阵,即使度很小,寻找邻点也可能需要扫描整整一行。因此直接的矩阵实现所需时间是顶点数的二次函数。数学上的距离定理依然成立,但计算上的界取决于表示方式。
最短距离的一个简短证书
搜索的输出可以在不重放队列的情况下加以验证。在已到达的顶点上,检查:源点的标号为零;每个其他顶点都有一个标号小一的父结点;父链接能到达源点;并且已到达顶点之间的每条边使标号的变化至多为一。此外还要检查没有边离开所声称的已到达集合。父链接提供了具有所记录长度的实际路径,而边的条件则为任何竞争路径提供了下界。
证明
(父路径给上界,边不等式给下界)
为看出下界,沿任意一条从源点出发的路径走。在第一个顶点处标号为零,每经过一条边,标号至多增加一。因此经过给定条数的边之后,终点的标号不大于该条数。于是每条源点路径的长度都至少等于其终点的标号。父结点路径达到了这个界,所以标号恰好是最短距离。检查没有边离开已到达集合,则保证了被遗漏的顶点确实不可达。
证明透视
最短路径需要上界和下界
每项局部检查各有其作用。父结点条件(标号小一、父链接到达源点)为每个已到达顶点构造一条实际路径,其长度等于其标号:这是上界。边的条件说明沿每条边标号至多变化一,所以沿任何源点路径,终点标号不大于所用的边数:这是下界,而且它约束每条竞争路径,不只是父结点树中的路径。源点标号为零为两个界提供起点。
封闭性检查,即没有边离开已到达集合,使下界能够覆盖所有源点路径:若缺少它,路径可能走出带标号的集合,而边的条件在那里不起作用,被遗漏的顶点也可能其实可达。仅有一棵看似合理的父结点树只能证明可达性,并不能证明最短路径。
距离层与二分图
若图的顶点可以分成两个集合,使得每条边都连接不同集合中的顶点,则称该图是二分的。在一个连通分支中,BFS 提示了一种候选划分:把距离为偶数的顶点放在一侧,距离为奇数的顶点放在另一侧。若每条边都跨越这一划分,它就是一个有效的二分划分。若有一条边连接了距离奇偶性相同的顶点,则该分支不可能有二分划分。
证明
(奇偶性沿每条路径被迫确定)
为证明不可能性的断言,假设存在二分划分。沿着任意一条路径,每经过一条边,所属的一侧就交替一次。从源点出发,每条偶数长度的路径必终止于源点所在的一侧,每条奇数长度的路径必终止于相反的一侧。特别地,每个 BFS 最短距离的奇偶性将决定其所在的一侧。于是连接奇偶性相同的顶点的边就会连接同一侧的顶点,与二分划分的定义矛盾。这证明了该检验,而无需假设图形的画法或某种特定的父结点选择。
对于不连通的图,要在每个分支中进行检验;在每个分支内部,两侧可以单独对调。三角形不通过检验,因为源点的两个邻点具有相同的奇数距离且彼此相邻。四圈通过检验,因为它交替的层给出了一个有效的划分。这些例子也说明,图的顶点数为偶数本身并不是二分性的条件。
概念视角结构
距离标号组织了几个问题
同样的 BFS 层既回答最短距离问题,又提供父结点路径,还按奇偶性给出一种二着色的候选。这些是对同一个带标号结构的相关用法,但每个结论都需要各自的检验。距离的正确性来自队列不变量;二分性则还要求每条边都符合奇偶性。
常见错误
常见错误
(图形中的交叉不是顶点)
图形中边的交叉并不产生顶点,除非明确把它声明为顶点。还要区分最短路径与转弯最少的路径或视觉上最短的曲线:这里每条边的长度都是一。
常见错误
(把队列换成栈)
FIFO 队列是必不可少的。把它换成栈就得到深度优先搜索,它可能首先沿着较长的路径发现某个顶点。
常见错误
(在带权图上使用 BFS)
带权图需要不同的距离论证:一条权很大的边可能比几条权很小的边更差。若 、,BFS 经直接边把 标为 ,但最便宜的路线 代价只有 。BFS 的定理假设所有边的代价相等。
总结
树在任意两个顶点之间有唯一的路径,且边数恰比顶点数少一。这些计数需要结构性的假设。BFS 保持着队列分层的不变量,使得首次发现时就给出无权最短距离;父结点的选择可以不同,而距离保持不变。
练习
快速检查
(证明:有十个顶点、三个连通分支的森林有七条边。)
孤立顶点算作单顶点的分支。
解答 · 答案
设各分支的大小为 ,其和为 。每个分支都是树,所以有 条边,当 时为 条。相加得 条边。不同分支之间没有边,所以所有的边都已被计入。
快速检查
(给出一个图,使深度优先发现可能记录下一条非最短的源点路径,并说明 BFS 给出的不同距离。)
请指明邻点的顺序,使搜索没有歧义。
解答 · 答案
取边 。设深度优先搜索从 出发先递归探索 再探索 ,然后从 探索 ,再从 探索 。它首次发现 时经过的路径长度为 ,尽管边 给出的距离是 。BFS 在处理 时同时发现 ,因此令 。
快速检查
(在边为 的图上从 开始执行 BFS,按字母顺序扫描邻点。记录标号与父结点,并用奇偶性检验判断它是否为二分图。)
检查每一条边,而不只是父边。
解答 · 答案
处理 时发现 与 ,标号为 ,父结点为 。处理 时发现 ,标号为 ,父结点为 ; 已被发现。处理 时发现 ,标号为 ,父结点为 ; 已被发现。标号为 、、。父边 都连接奇偶性不同的顶点,但边 连接两个标号为 的顶点。因此该图不是二分图;事实上 构成三角形,是一个奇圈。