网络在失去一条连线后可能仍然连通;树则处于另一极端:它连通,而且每条边都是不可缺少的。本节说明这一局部性质与不含圈的整体性质为何等价。
定义
定义 1.1.1
(游走、路径、圈与桥)
有限简单无向图是二元组 ,其中 有限, 是由 的二元子集组成的集合。游走是相邻顶点依次相接的顶点序列;路径是不重复顶点的游走。长度为零的路径将顶点与自身连接。若任意两顶点之间都有路径,则图是连通的。圈是长度至少为三、除首尾相同外不重复顶点的闭游走。删除边 后若连通分支数增加,则称 为桥。
定理 1.1.2
(桥的判别法)
一条边是桥,当且仅当它不属于任何圈。
证明
(绕圈改道的证明)
设 。若 属于某圈,去掉它后圈的其余部分仍给出一条从 到 的路径。将任意游走中经过 的部分换成这条路径,再删去重复段,就能得到不经过 的路径。因此删除 不会拆开原来的分支。反过来,若 不是桥,则删除后 仍然连通;否则原来包含 的分支会分裂,因为其两侧之间原有的每条路径都必须经过 。取一条不含 的 到 路径,加上 便成一个圈。
拼接两条路径可能重复顶点,因此先得到的是游走。若一个有限游走重复顶点,就删除该顶点两次出现之间的一段;反复操作便得到同端点的路径。
定理/命题
定义 1.1.3
(树与森林)
树是至少有一个顶点的连通无圈有限简单图。森林是无圈图;它的每个分支都是树,孤立顶点也算一个分支。
定理 1.1.4
(树的刻画)
对有 个顶点的图,下列条件等价:
- 图是树。
- 任意两顶点之间恰有一条路径。
- 图连通且有 条边。
- 图无圈且有 条边。
证明
(经由叶、生成树与森林计数的证明)
在树中,连通性保证存在路径;若两条不同路径有相同端点,从首次分岔处走到下一次相遇处便形成圈。因此 (1) 推出 (2)。反之,圈上相邻的两个顶点之间有两条路径,所以唯一性排除圈,(2) 推出 (1)。
至少有两个顶点的有限树必有度为一的顶点,称为叶。取最长路径:端点不能有路径外的邻点,否则可以延长;也不能有路径上其他邻点,否则会形成圈。删除该叶及其边后,剩下的图仍连通且无圈:连接剩余顶点的路径不能以叶为内部顶点。从单顶点树开始归纳,得到树有 条边,故 (1) 推出 (3) 与 (4)。
任何有限连通图都有生成树:只要有圈,就删除圈上一条边。桥的判别法说明删除后仍连通;边数有限,所以最后得到连通无圈的生成子图。它有 条边,因此原图若恰有这么多边,就等于它的生成树,即 (3) 推出 (1)。最后,森林若有 个分支,其顶点数分别为 ,则边数为 。无圈且有 条边便迫使 ,所以图是树,即 (4) 推出 (1)。
证明透视
每个推出关系用不同的工具
(1) 与 (2) 的等价只用到分岔论证:两条端点相同的不同路径含有圈,而一个圈提供两条路径。边数依赖叶的引理,有限性正是在这里、通过选取最长路径而用到;归纳每次删去一片叶和一条边,并保持是树。
逆命题需要的是构造而不只是计数。对 (3),生成树是删去圈上的边得到的,而桥的判别法正好保证每次删除都不会使图不连通;生成树有 条边,原图也不多于此数,所以实际上没有删去任何边。对 (4),计数逐个分支进行,,而假设 迫使 。两个逆命题中,边数都只有与第二个性质((3) 中的连通性、(4) 中的无圈性)配合才起作用。
边数条件中伴随的性质都不能省去。
反例模式
只有边数不能刻画树
这里排除空图,避免对空图是否连通的约定产生歧义。只有 条边还不够:三角形加一个孤立顶点有四个顶点、三条边,却既不连通又含圈。
例题详解
例题 1.1.5
(带尾巴的三角形的桥与生成树)
令 ,,其中以 简记 。三角形的边都在圈上,所以都不是桥; 不在任何圈上,是桥。删除 得到路径 ,它是一棵有三条边的生成树。删除 却会孤立 ,这说明了桥的判别法的作用。生成树通常不唯一,例如删除 也能得到另一棵。
练习
快速检查
(森林有 个顶点和 条边,求分支数。)
解答 · 答案
由 得 。孤立顶点也要计作分支。
快速检查
(连通图有 个顶点和 条边。证明它恰有一个圈。)
解答 · 答案
取生成树 ,它有 条边,所以图中恰有一条不属于 的边 。树中唯一的 到 路径与 一起构成一个圈。任何圈都必须含树外的边,因此必须含 ;去掉 后剩下 中的一条 到 路径,唯一性迫使它就是前述路径。所以恰有一个圈。
向树添加一条边
定理 1.1.6
(向树添加一条边恰产生一个圈)
设 是树, 是不相邻的不同顶点。添加边 后恰好产生一个圈,它由树中唯一的 到 路径与新边构成。
证明
(由树中路径唯一性的证明)
树中唯一的 到 路径与新边构成圈。扩充图的任何圈都必须经过新边,因为原树无圈;去掉新边后,圈余下部分是树中从 到 的路径,树的刻画迫使它就是上述路径。
这给出一种交换操作:删除该圈上除新边以外的任意一条边,仍得到生成树。确实,原来经过被删边的游走可改走圈的其余部分,因此图仍连通;它有 条边,所以是树。这里不能任意删除圈外的边。
概念视角结构
极小连通图与极大无圈图
树恰好是极小连通图:图连通,并且每条边都是桥;由桥的判别法,“没有边在圈上”与“每条边都是桥”说的是同一件事。对偶地,树恰好是极大无圈图:图无圈,并且在任意两个不相邻顶点之间加边都会产生圈,这就是上面的定理。反过来,极大无圈图必定连通,因为连接两个分支的边不会产生圈。
例题 1.1.7
(路径上的一次交换)
从路径 开始,添加 ,唯一的圈为 。删除 后得到边 ;新树中从 到 的唯一路径为 。如果原树另有叶 ,仅以 相连,那么 不在这个圈上,删除它会孤立 。
计数与构造是不同的问题
常见错误
(未知无圈就使用森林计数)
公式 用来计算森林的分支数,使用前必须先知道图无圈。例如两个不相交的三角形有六个顶点、六条边和两个分支,而 。圈上的边增加了冗余,却不改变连通性,因此仅靠边数不能看出分支结构。
不用枚举所有边的子集也能构造生成树。从连通有限图的一个顶点出发,每次选择恰有一个端点已到达的边,加入另一个端点。只要仍有未到达顶点,这种边就存在:取一条从已到达顶点到未到达顶点的路径,选它首次离开已到达集合的边。每步增加一个顶点和一条边,且新顶点在构造出的子图中只有一条边,所以不会产生圈。最终得到生成树。不同选择可能得到不同的树;这并不保证总权重最小。
例题 1.1.8
(从同一顶点长出的两棵生成树)
对正方形 加对角线 ,从 开始,依次选 ,得到一棵生成树;选 又得到另一棵。没有指定权重及优化算法,就不能断言哪棵最便宜。
补充练习
快速检查
(一棵树有 个顶点,向两个原本不相邻的顶点间添加一条边。要恢复同顶点集上的树,须删去多少条边?哪些边可以删除?)
解答 · 答案
扩充图有 条边,而同顶点集的树有 条,因此恰须删去一条。删除新边或唯一圈上的任意边都可以,因为圈的其余部分保持其端点连通。删除圈外边不行:删去它会把原树分成两部分,而新边的端点仍在同一部分,因为原来连接它们的路径不经过被删边。
快速检查
(证明至少有两个顶点的树至少有两片叶。)
解答 · 答案
取最长路径。前述证明适用于它的两个端点,所以两端度数都是一;由于树至少有两个顶点,它们互不相同。这里有限性不可省略:双向无限路径没有叶。
树中的度数计数
有限简单图的每条边对两个端点的度数各贡献一,因此 。对 的树,减去每个顶点的 得到
设叶的数目为 。每片叶贡献 ,度为二的顶点贡献零,度至少为三的顶点贡献正整数,所以
这比至少有两片叶更强:一个度为四的顶点迫使至少有四片叶。公式必须排除单顶点树:其唯一顶点度数为零,贡献 ,而不是叶所贡献的 。
例题 1.1.9
(一个度为四的顶点迫使的叶数)
一棵树恰有一个度为四的顶点,其余顶点度数为一或二。公式给出 。它不能确定度为二的顶点有多少:细分任何一条边都会插入一个度为二的顶点,却不改变叶数。五顶点星形树与细分其中一条边所得的树都符合条件。
快速检查
(一棵树有六片叶、两个度为三的顶点、一个度为四的顶点,其余顶点度数为二。这些度数能否出现?)
解答 · 答案
叶数公式要求 ,所以计数相容。要证明存在而不仅是必要条件相容,可以把度为四的顶点与两个度为三的顶点及两片叶相连,再在每个度为三的顶点上各接两片叶。所得连通无圈图具有指定度数;细分边可加入度为二的顶点。单凭数值恒等式相容不能证明存在。
常见错误
常见错误
(证明无圈时先假设路径唯一)
证明关于树的结论时,要分清两个定义性质各自起什么作用。连通性保证路径存在,却不能单独保证路径唯一:三角形相邻顶点之间有两条路径。无圈性保证已有路径的唯一性,却不能保证不同分支之间存在路径。在证明连通图无圈时先假设路径唯一,就是循环论证。
单顶点图同时满足两个条件且没有边,是边数归纳证明的起点。对森林,这些推理必须分别应用于每一个连通分支,孤立顶点也不例外。