运筹学讲义 §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 相连