7.1 无向树及其性质
本章目录 · 1 节
本章导读
【定义7.1.1:树与森林】连通且没有圈的无向简单图称无向树,简称树;每个连通分支都是树的图称森林。平凡图 是平凡树。非平凡树中的1度顶点称树叶,度数至少2的顶点称分支点;平凡树的唯一顶点度数为0,不按本书的“悬挂顶点”定义算树叶。
本章“无回路”特指没有非空的简单回路或初级回路,即没有圈;不是说不允许“沿一条边出去再沿原边回来”的重复边闭合通路,否则任何有边图都会被错误排除。下文“唯一的路径”指顶点不重复的初级通路,不能换成任意允许来回绕行的通路。
【定理7.1.1:六种等价判定】设 是顶点数 、边数 的无向简单图,以下六条等价。
(1) 是树。
(2)任意两个不同顶点之间存在唯一一条路径。
(3) 无圈,且 。
(4) 连通,且 。
(5) 连通,且每条边都是桥。
(6) 无圈,在任意两不同顶点之间添加一条有新身份的边后,产生唯一一个含新边的圈。若两点本已有边,新边允许与其平行,此时产生二圈;若坚持添加后仍为简单图,则把这一操作限定到不相邻的两点,等价结论仍成立。
【等价性的证明链】(1)推出(2):连通保证有路径;若有两条不同路径,取它们第一次分开后再次相遇的部分就组成圈,与无圈矛盾。
(2)推出(3):若有圈,圈上两不同顶点之间沿圈两方向都给出路径,违背唯一性。再对 归纳计数: 时 ; 时任删一边,因为没有圈,该边必为桥,把图分成两棵较小的连通无圈图。设它们顶点数 ,边数分别 ,加回原边得 。
(3)推出(4):若无圈图有 个连通分支,每个分支按定义都是树,且由前两步每棵树的边数为阶数减1。因此 ;与 比较得到 ,即连通。这个公式同时说明一般森林满足 。
(4)推出(5):若有边不是桥,删去它仍连通,却只剩 条边,与连通图至少 条边的结论矛盾。因此每条边都是桥。
(5)推出(6):若存在圈,圈上边都不是桥,矛盾,所以 是树,任意两点间有唯一路径。新边与该路径组成一个圈;含新边的另一个圈将给出原图另一条路径,故不可能。
(6)推出(1):原图已无圈;任取两不同点 ,加边 后产生的圈删去新边,得到原图中的 路径,所以图连通。 按平凡树约定单独成立。至此六条构成闭合的证明链。
注意不能只用“边数 ”单独判树:一个三角形加孤立点有4个顶点、3条边,却既不连通又有圈。也不能把连通条件或无圈条件在(3)、(4)中任意省掉。
【定理7.1.2:至少两片树叶】每棵 的树至少有两片树叶。设树叶数为 。树连通,无0度点;其余 个点度数至少2。由握手定理及 ,有 ,故 。平凡树不在这个结论范围内。
【例7.1.1:六阶树的全部非同构类型】六阶树有5边、度数和10,所有度数均正。给每点先分配1度后,还剩4度要分配,因此可能的非降度数列只有 、、、、 五种。
是星形图 。
有唯一4度点,四条分支中恰一条延长一次,其余直接接树叶,所以只有这一类。
的两个3度点必须相邻,否则连接它们的路径中还需要一个2度点,度数列却没有;各中心再各接两片树叶,只有这一类。
度数列 对应两类:从唯一3度中心出发,三条臂的长度分配为 或 。前者两个2度点相邻,后者不相邻,故不同构。这也说明相同度数列并不能保证树同构。
最后一列只有两个1度点、其余全2度,连通且无圈,所以必是路径 。五种度数列中只有一种分成两类,合计恰6棵,不能漏掉 之一。(例完)
【星形图】 时,只有一个分支点、且它的度数为 的树称星形图,该点称星心。它就是一个点连接其余全部 点的 。 是六阶星形图;星形图与“把线条画成星状的其他图”不是同一个定义。
【例7.1.2:饱和碳氢化合物的结构异构】考虑无环饱和烃 ,碳价4、氢价1,各化学键按无向边表示,同一个分子必须是连通图。图有 个顶点,度数和为 ,所以边数为 ,恰为顶点数减1。由连通性和定理7.1.1,它是树;不能只凭度数和就断言任意图都是树。
删去氢原子,剩下碳骨架仍连通且无圈;碳骨架每个点度数不超过4,剩余价键补接氢即可。于是问题转成求 阶、最大度至多4的碳骨架树的非同构类型。这里讨论连接方式造成的结构异构,不把同一结构在纸上的旋转、翻转另算一种。
:只有甲烷 一种。
:碳骨架只能是一条边,只有乙烷 一种。
:碳骨架只能是三顶点路径,只有丙烷 一种。
:四阶树只有路径 和星 两类,分别对应正丁烷与异丁烷(2-甲基丙烷),共两种。图中每个C都恰有四条键,每个H恰有一条键;五幅结构图各自都完整保留全部氢,而非只画不标氢的骨架。(例完)
