运筹学讲义 §2.2.1树 1847年,克希霍夫在研究电网络方程时首次提出了树的概念 树(tree): a connected(连通的) and acyclic(无圈的) graph 平凡树( trivial tree):v=1的树,即K1(平凡图):非平凡树( nontrivial tree): otherwise 叶(leaf):树的悬挂点(度为1的顶点):分支点( branch vertex):度≥2的顶点 非同构的树 1 5
运 筹 学 讲 义 1 §2.2.1 树 1847 年，克希霍夫在研究电网络方程时首次提出了树的概念. 树(tree)：a connected(连通的) and acyclic(无圈的) graph. 平凡树（trivial tree）： =1 的树，即 K1 （平凡图）；非平凡树（nontrivial tree）：otherwise. 叶（leaf）：树的悬挂点（度为 1 的顶点）；分支点（branch vertex）：度 2 的顶点. 非同构的树 1 2 3 4 5
运筹学讲义 个 注:(1)若v是树T的顶点,则v是树T的割点→d(v)≥2分v是树T的分支点,v不是树T 的割点分→d()=1v是树T的叶;树的每一条边均为割边 (2)若T是树,则vv∈V(T),T-v为森林,T-ν的各个连通分支都是树(见§2.2.1),称 之为T的子树( subtree (3)树是二分图.(∵树无圈,当然也不含有奇圈,见§2.1.2Th1).当然,森林也是二分图 2 树的应用背景 (1)概率树( probability tree) 车间050正品 次品 06正品 二车间040次品 07°正品 三车间03°次品 概率树在概率论上利用全概率公式, Beyes公式计算概率时作用甚大 (2)组织结构
运 筹 学 讲 义 2 6 7 11 个 注：（1）若 v 是树 T 的顶点，则 v 是树 T 的割点 d(v) 2 v 是树 T 的分支点， v 不是树 T 的割点 d(v) = 1 v 是树 T 的叶；树的每一条边均为割边. （2）若 T 是树，则 v V(T) ，T −v 为森林， T −v 的各个连通分支都是树（见§2.2.1），称 之为 T 的子树（subtree）. （3）树是二分图.（ 树无圈，当然也不含有奇圈，见§2.1.2 Th1）.当然，森林也是二分图 树的应用背景： （1）概率树（probability tree） 概率树在概率论上利用全概率公式，Beyes 公式计算概率时作用甚大. （2）组织结构
运筹学讲义 学校 院系 班级班级班级 (3)家谱( family tree):家谱反映的家族内部的血缘关系和树的特征(连通,无圈)一致 (4)化学物质的结构:同分异构体 1857年,数学家凯莱( Arthur Cayley)利用树的概念来研究烃的同分异构体. H 顶点表示碳原 子,边表示原子 HHH 之间的化学键. 丙烷C3F C一H HHH H H H-c一H 丁烷C4H10的两种同分异构体 (5)决策树( decision tree) (6)在计算机上, Windows操作系统采用树形结构管理文件与目录系统. Lemma1任一非平凡树均至少有两个悬挂点.(任一非平凡树均至少有两个叶) 证明:设T是一个树,v≥2,取T的一条最长路P=1v2…V4-vk
运 筹 学 讲 义 3 （3）家谱（family tree）：家谱反映的家族内部的血缘关系和树的特征（连通，无圈）一致. （4）化学物质的结构：同分异构体 1857 年，数学家凯莱（Arthur Cayley）利用树的概念来研究烃的同分异构体. 顶点表示碳原 子，边表示原子 之间的化学键. 丁烷 C4H10 的两种同分异构体 （5）决策树（decision tree）： （6）在计算机上，Windows 操作系统采用树形结构管理文件与目录系统. Lemma1 任一非平凡树均至少有两个悬挂点.（任一非平凡树均至少有两个叶） 证明：设 T 是一个树， 2 ，取 T 的一条最长路 k k P v v v v = 1 2 −1
运筹学讲义 ∵≥2,且T连通,P的长度为v≥1,于是v1≠v 下证v1是悬挂点,即d(v1)=1 (反证法)假设d(v1)≥2,则彐vm∈V(,Vm≠v1,使得v1vm∈E(T) 若vn∈P,则令P=P+v1vn,显然P是7的一条路,且比P的长度多1,与P是最长路矛 若vn∈P,则v1v2…vnv1是T的一个圈,与T是树矛盾 同理可证,v也是悬挂点 另证:设非平凡树T的悬挂点的个数为x,则非悬挂点的个数为v-x 由§21.1Th1有,2V-1)=2E=∑()21x+2(v-x)→x22■ 注:非平凡树的最长路的起点和终点必为悬挂点 Lemma2(1)若图G无孤立点,且E≤v-1,则G至少有一个悬挂点 (2)若图G连通,且E≤v-1,则G至少有一个悬挂点 证明:(1)(反证法)假设G无悬挂点,则由G无孤立点知,Vv∈V,d(v)≥2,i=1,2,…P 于是,2=2(m)≥22=21→B≥矛盾 (2)若G连通,则G无孤立点,故由(1)知,G至少有一个悬挂点 注:(逆否命题)若图G无孤立点,且无悬挂点,则q≥P;若图G连通,且无悬挂点,则q≥p Th1(1)T是树;◇(2)T无圈,且E=v-1:◇(3)T连通,且E=v-1;(4)T 的任两顶点之间恰有唯一一条路相连;◇(5)T连通,且去掉任一条边后即不连通;(6)T无 圈,且在任两顶点之间添加一条边即得一个圈 证明:(1)◇(2):→设T是树,则T无圈:下证E=v-1
运 筹 学 讲 义 4 2 ，且 T 连通， P 的长度为 1 ，于是 k v v 1 . 下证 1 v 是悬挂点，即 d(v1 ) =1. （反证法）假设 d(v1 ) 2 ，则 1 v V(T), v v m m ，使得 ( ) v1 vm E T . 若 vm P ，则令 m P P v v = + 1 ，显然 P 是 T 的一条路，且比 P 的长度多 1，与 P 是最长路矛 盾； 若 vm P ，则 1 2 1 v v v v m 是 T 的一个圈，与 T 是树矛盾. 同理可证， k v 也是悬挂点. 另证：设非平凡树 T 的悬挂点的个数为 x ，则非悬挂点的个数为 − x . 由§2.1.1 Th1 有， 2( −1) = 2 = ( ) 1 + 2( − ) 2 d v x x x v V .▌ 注：非平凡树的最长路的起点和终点必为悬挂点. Lemma2(1)若图 G 无孤立点，且 −1 ，则 G 至少有一个悬挂点． (2)若图 G 连通，且 −1 ，则 G 至少有一个悬挂点． 证明：(1)（反证法）假设 G 无悬挂点，则由 G 无孤立点知， vi V,d(vi ) 2,i =1,2, , p . 于是， = = = = 2 ( ) 2 2 1 1 p i p i i d v ，矛盾. (2)若 G 连通，则 G 无孤立点，故由（1）知， G 至少有一个悬挂点.▌ 注：（逆否命题）若图 G 无孤立点，且无悬挂点，则 q p ；若图 G 连通，且无悬挂点，则 q p ． Th1（1） T 是树； （2） T 无圈，且 = −1 ； （3） T 连通，且 = −1 ； （4） T 的任两顶点之间恰有唯一一条路相连； （5） T 连通，且去掉任一条边后即不连通； （6） T 无 圈，且在任两顶点之间添加一条边即得一个圈. 证明：（1） （2）： 设 T 是树，则 T 无圈；下证 = −1
运筹学讲义 (对v作数归法)当v=1,2时,结论显然成立 设当v=k时结论成立,则当v=k+1时,令v(T)=k+1,则由Thl v知,T至少有两个悬挂点不妨取其一为v,则易见T-v仍是树,且 (7-v)=k 由归纳假设,有E(T-v)=(T-v)-1=k-1 于是,E(T)=E(T-)+1=k-1+1=k=v(T)-1.综上,E 仁设T无圈,且E=ν-1,则仅需证T连通.(反证法)假设T不连通,则o(T)≥2.不妨设T的 各连通分支为T1,T2,…,T。,则易见T是树,且由(1)→(2)知,E(T)=v(T)-1,=1,2,…,O c≥2 于是,6()=∑a(7)=∑[(T)-1=∑()-0=v()-0≤(7)-2,与E=v-1矛盾 (1)分(3):→设T是树,则T连通:再由(1)→(2)知,E=V-1 ←设T连通,且E=v-1,则仅需证T无圈 (对v作数归法)当v=1,2时,E=0,1,T显然无圈; 设当v=k时无圈性成立,则当v=k+1时,令v(T)=k+1 E(T)=E(T)-1=k,则由Lema2(2)知,T至少有一个悬挂点不 妨设它为v,则易见T-v仍连通,且v(T-v)=(T)-1=k, T-v)=E(T)-1=k-1=v(T-v)-1 由归纳假设知,T-ν无圈.显然,T亦无圈.综上,T无圈得证 (1)◇(4):→设T是树,则T连通,∴T的任两顶点之间必至少有一条路相连 下证唯一性(反证法)假设彐u,v∈V(T),a,v之间有两条不同的路P,Q相连
运 筹 学 讲 义 5 （对 作数归法）当 = 1,2 时，结论显然成立； 设当 = k 时结论成立，则当 = k +1 时，令 (T) = k +1 ，则由 Th1 知， T 至少有两个悬挂点.不妨取其一为 v ，则易见 T −v 仍是树，且 (T − v) = k . 由归纳假设，有 (T − v) = (T − v) −1 = k −1. 于是， (T) = (T − v) +1 = k −1+1 = k = (T) −1.综上， = −1 成立. 设 T 无圈，且 = −1,则仅需证 T 连通.（反证法）假设 T 不连通，则 (T) 2 .不妨设 T 的 各连通分支为 T T T , , , 1 2 ，则易见 Ti 是树，且由（1） （2）知， (Ti ) = (Ti ) −1,i = 1,2, , . 于是， ( ) ( ) [ ( ) 1] ( ) ( ) ( ) 2 2 1 1 1 = = − = − = − − = = = T T T T T T i i i i i i ，与 = −1 矛盾. （1） （3）： 设 T 是树，则 T 连通；再由（1） （2）知， = −1. 设 T 连通，且 = −1 ，则仅需证 T 无圈. （对 作数归法）当 = 1,2 时， = 0,1，T 显然无圈； 设当 = k 时无圈 性成 立， 则当 = k +1 时， 令 (T) = k +1 ， (T) = (T) −1 = k ，则由 Lemma2（2）知， T 至少有一个悬挂点.不 妨设它为 v ，则易见 T −v 仍连通，且 (T − v) = (T) −1 = k ， (T − v) = (T) −1 = k −1 = (T − v) −1. 由归纳假设知， T −v 无圈.显然， T 亦无圈.综上， T 无圈得证. （1） （4）： 设 T 是树，则 T 连通， T 的任两顶点之间必至少有一条路相连. 下证唯一性.（反证法）假设 u,v V(T) ，u, v 之间有两条不同的路 P,Q 相连
运筹学讲义 y P 若P与Q无公共边,则P+Q恰为T的一个圈,与T是树矛盾;否则,彐e=xy∈E(P)\E(Q) 显然,(P+Q)-e连通,故(P+Q)-e中彐一条(x,y)-路W.于是,W+e是T的一个圈,与T是 树矛盾 ←设T的任两顶点之间恰有唯一一条路相连,则T连通.下证T 无圈.(反证法)假设T中有一个圈C=v1v2…Vxv4V1,则vvk 与C-v1vk是连结顶点v1,v的两条不同的路,与唯一性矛盾. k-1 (1)分(5):→设T是树,则T连通.下证去掉T的任一条边后即不连通 (反证法)假设彐e=∈E(T),使得T-e仍连 通,则u,v之间有一条路P相连.于是,P+e是T 的一个圈,与T是树矛盾. ←设T连通,且去掉任一条边后即不连通,则仅需证T无圈. (反证法)假设T中有一个圈C=v1V2…vh=vv1,则易见 ve∈E(C),T-e仍连通,矛盾 1)(6):→设T是树,则T无圈.下证在T的任两顶点之间添加一条边即得一个圈. Va,∈(T),由T是树知,T连通,∴l,v之 v间有一条路P相连.在T中添加边m,则P+m 即为T+n的一个圈
运 筹 学 讲 义 6 若 P 与 Q 无公共边，则 P + Q 恰为 T 的一个圈，与 T 是树矛盾；否则， e = xy E(P) \ E(Q) . 显然， (P + Q) − e 连通，故 (P + Q) − e 中 一条 (x, y) −路 W .于是， W + e 是 T 的一个圈，与 T 是 树矛盾. 设 T 的任两顶点之间恰有唯一一条路相连，则 T 连通.下证 T 无圈.（反证法）假设 T 中有一个圈 1 2 1 1 C v v v v v = k− k ，则 k v v1 与 k C v v − 1 是连结顶点 k v ,v 1 的两条不同的路，与唯一性矛盾. （1） （5）： 设 T 是树，则 T 连通.下证去掉 T 的任一条边后即不连通. （反证法）假设 e = uv E(T) ，使得 T −e 仍连 通，则 u, v 之间有一条路 P 相连.于是， P + e 是 T 的一个圈，与 T 是树矛盾. 设 T 连通，且去掉任一条边后即不连通，则仅需证 T 无圈. （反证法）假设 T 中有一个圈 1 2 1 1 C v v v v v = k− k ，则易见 e E(C) ，T −e 仍连通，矛盾. （1） （6）： 设 T 是树，则 T 无圈.下证在 T 的任两顶点之间添加一条边即得一个圈. u, v V (T) ，由 T 是树知，T 连通， u, v 之 间有一条路 P 相连.在 T 中添加边 uv ，则 P +uv 即为 T +uv 的一个圈
运筹学讲义 仁设T无圈,且在任两顶点之间添加一条边即得一个圈,则仅需证T连通 l v,v∈V(T),在T中添加边ny,则T中有一个圈,不妨设为C. 易见,∈E(C).于是,C-n即为连结u,ν的一条路,故T连 通 注:(1)树的边数是E=v-1 (2)Th1(5)表明:就连通性而言,树的边数最少.∴树是极小连通图( minimal connected graph), 即在顶点数相同的所有连通图中,树含有的边数最少 6)表明:就无圈性而言,树的边数最多.∴树是极大无圈图( maximal acyclic graph),即在 顶点数相同的所有无圈图中,树含有的边数最多 Th2 A connected graph g is a tree if and only if every edge of g is a cut edge. 证明:→ Assume g is a graph,ye∈E,∵ G is acyclic,∵by02-01(2)割边的定义的注 (3),e is a cut edge c(By contradiction)Suppose G is not a tree, then G contains at least a cycle C. By §2.1.2割边的定义的注(3), the edges of C are not cut edge of C, which contradicts the hypothesis. Note:§2.1.2割边的定义的注(3): e is a cut edge of a graph G分 e dosen' t belong to any cycle of G Th3设树中度为的顶点的个数为v,1=12…,△,△≥2,则叶的个数为v1=2+∑(-2)v 证明:由§2.1.1Th1有, ∑v=∑4()=26=2(-1)=2∑v-1)→2+∑(-2)1=0 →2-v1+∑(-2川=0→v=2+∑(-2) 注:叶的个数竟然与度为2的顶点的个数无关!(为什么?) 例1一个树中度为2,3,4的顶点的个数分别为2,1,3,其余顶点为叶,求叶的个数 解:设叶的个数为x,则v=x+2+1+3 由§2.1.1Th1有,1·x+2×2+3×1+4×3=2(x+2+1+3-1)→x=9 7
运 筹 学 讲 义 7 设 T 无圈，且在任两顶点之间添加一条边即得一个圈，则仅需证 T 连通. u, v V (T) ，在 T 中添加边 uv ，则 T 中有一个圈，不妨设为 C . 易见， uv E(C) .于是， C −uv 即为连结 u, v 的一条路，故 T 连 通.▌ 注：（1）树的边数是 = −1. （2）Th1（5）表明：就连通性而言，树的边数最少. 树是极小连通图（minimal connected graph）， 即在顶点数相同的所有连通图中，树含有的边数最少； （6）表明：就无圈性而言，树的边数最多. 树是极大无圈图（maximal acyclic graph），即在 顶点数相同的所有无圈图中，树含有的边数最多. Th2 A connected graph G is a tree if and only if every edge of G is a cut edge. 证明： Assume G is a graph, e E , G is acyclic, by 02-01(2)割边的定义的注 （3）, e is a cut edge. (By contradiction)Suppose G is not a tree, then G contains at least a cycle C .By §2.1.2 割边的定义的注（3）,the edges of C are not cut edge of G , which contradicts the hypothesis.▌ Note:§2.1.2 割边的定义的注（3）： e is a cut edge of a graph G e dosen’t belong to any cycle of G . Th3 设树中度为 i 的顶点的个数为 i ，i = 1,2, , ， 2 ，则叶的个数为 = = + − 3 1 2 ( 2) i i i . 证明：由§2.1.1 Th1 有， = = = = = − + − = = + − = = = − = − + − = 3 1 3 1 1 1 1 2 ( 2) 0 2 ( 2) ( ) 2 2( 1) 2( 1) 2 ( 2) 0 i i i i i i i i i v V i i i i d v i ▌ 注：叶的个数竟然与度为 2 的顶点的个数无关！（为什么？） 例 1 一个树中度为 2，3，4 的顶点的个数分别为 2，1，3，其余顶点为叶，求叶的个数. 解：设叶的个数为 x ，则 = x + 2+1+3. 由§2.1.1 Th1 有， 1 x + 2 2 + 31+ 43 = 2(x + 2 +1+ 3 −1) x = 9
运筹学讲义 另解:由Th3有,v1=2+∑(-2川1=2+(3-2),1+(4-2)3=9■ 注:将例1改为:“度为3,4的顶点的个数分别为1,3”亦可解 例2一个树有20个顶点,其中有8个叶,其余顶点的度均≤3,求2,3度顶点的个数 解:易见,除叶外,树的其余顶点的度均为2,3.设2度顶点的个数为x,则由§2.1.1Th1有, 1×8+2x+3(20-8-x)=2·(20-1)→x=6.∴3度顶点的个数为20-8-6=6. 例3求证:恰含有2个悬挂点的树必为一条路 证明:只需证树中除两个悬挂点外的顶点的度均为2.(反证法)假设树中存在度>2的顶点,则 有2(-1)=2E=∑d()>1×2+2(-2)→0>0,矛盾■ 例4求证:若T是树,且Δ≥k(k∈N),则T中至少有k个悬挂点 证明:(反证法)假设T中悬挂点的个数为s,则 2(v-1)=2E=∑()21s+△+2(-s-1)=2(-1)+△-s→s≥△≥k 例5求证:若树中度为的顶点的个数v,i=12,…,△,△≥2,则v≥v,i=3,…,△,但 v1与v2大小不定 证明:2(v1+v2+v3+v4…+v4-1)=2(v-1)=2E=∑d(v) l·v+2·v2+3·v3+4·v4…+△v →v=v3+2v4…+(A-2)+2→v≥v,i=3 但v与v大小不定 另证:由Th3有,=2+∑(-2川1→V=v3+2V4…+(4-2)+2→v≥v, 例6烷烃是一种有机物,由碳原子和氢原子构成,其中碳,氢原子的化合价分别为4,1,且不 存在任何化学键构成圈.试证:烷烃的分子式为CnH2n+2 证:设烷烃的分子式为C,H,将碳,氢原子视为顶点,原子之间的化学键视为边,则烷烃的分
运 筹 学 讲 义 8 另解：由 Th3 有， 2 ( 2) 2 (3 2) 1 (4 2) 3 9 3 1 = + − = + − + − = i= i i .▌ 注：将例 1 改为：“度为 3，4 的顶点的个数分别为 1，3”亦可解. 例 2 一个树有 20 个顶点，其中有 8 个叶，其余顶点的度均 3 ，求 2，3 度顶点的个数. 解：易见，除叶外，树的其余顶点的度均为 2，3.设 2 度顶点的个数为 x ，则由§2.1.1 Th1 有， 18 + 2x + 3(20 − 8 − x) = 2 (20 −1) x = 6 . 3 度顶点的个数为 20 −8−6 = 6.▌ 例 3 求证：恰含有 2 个悬挂点的树必为一条路. 证明：只需证树中除两个悬挂点外的顶点的度均为 2.（反证法）假设树中存在度 2 的顶点，则 有 2( −1) = 2 = ( ) 1 2 + 2( − 2) 0 0 v V d v ，矛盾.▌ 例 4 求证：若 T 是树，且 k (k N) ，则 T 中至少有 k 个悬挂点. 证明：（反证法）假设 T 中悬挂点的个数为 s ，则 d v s s s s k v V − = = + + − − = − + − 2( 1) 2 ( ) 1 2( 1) 2( 1) .▌ 例 5 求证：若树中度为 i 的顶点的个数 i ，i = 1,2, , ， 2 ，则 1 i ，i = 3, , ，但 1 与 2 大小不定. 2 ( 2) 2 , 3, , , 1 2 3 4 : 2( 1) 2( 1) 2 ( ) 1 3 4 1 1 2 3 4 1 2 3 4 = + + − + = = + + + + + + + + − = − = = i d v i v V 证明 但 1 与 2 大小不定. 另证：由 Th3 有， = = + − 3 1 2 ( 2) i i i 1 = 3 + 4 + − + 2 1 i 2 ( 2) ， i = 3, , .▌ 例 6 烷烃是一种有机物，由碳原子和氢原子构成，其中碳，氢原子的化合价分别为 4，1，且不 存在任何化学键构成圈.试证：烷烃的分子式为 CnH2n+2 . 证：设烷烃的分子式为 CnHm ，将碳，氢原子视为顶点，原子之间的化学键视为边，则烷烃的分
运筹学讲义 子结构是一个含有n个4度顶点,m个1度顶点的树 由Th3有,m=2+∑(-2)1=2+(4-2)xn=2n+2 烷烃的分子式为CnH2n+2·■
运 筹 学 讲 义 9 子结构是一个含有 n 个 4 度顶点， m 个 1 度顶点的树. 由 Th3 有， 2 ( 2) 2 (4 2) 2 2 3 = + − = + − = + = m i n n i i . 烷烃的分子式为 CnH2n+2 .▌