《运筹学》课程PPT教学课件（Operations Research）第六章 图论（6.2）树

运筹学 Operations Research §6.2树 树(tre):连通的无圈的图 平凡树( trivial tree):v=1的树. 叶(leaf):树的悬挂点(度为1的顶点); 分支点( branch vertex):度≥2的顶点 2021/2/20

2021/2/20 1 运 筹 学 Operations Research §6.2 树 树(tree)：连通的无圈的图. 平凡树（trivial tree）：  = 1的树. 叶（leaf）：树的悬挂点（度为1的顶点）； 分支点（branch vertex）：度  2的顶点

运筹学 Operations Research =6的所有非同构的树: 2021/2/20 2

2021/2/20 2 运 筹 学 Operations Research  = 6的所有非同构的树：

运筹学 Operations Research 树的应用: (1)概率树( probability tree) 一车间050正品 0.5 次品 0.306正品 二车间04次 品 07正品 三车间030次品 2021/2/20 3

2021/2/20 3 运 筹 学 Operations Research 树的应用： （1）概率树（probability tree）

运筹学 Operations Research (2)组织结构 学校 院系 院系 班级班级班级 2021/2/20 4

2021/2/20 4 运 筹 学 Operations Research （2）组织结构

运筹学 Operations Research (3)在计算机上, Windows操作系统采用树形结构管理文 件与目录系统 创甜 卩文件⑥编辑查看收藏凸工具(①帮助出 后退→·间|③搜索乌文件夹③历史X2国 □甜 文件夹 我的文档 Matsoftware 趣味图论 我的电脑 由本地磁盘(E 习题解答运筹学讲义 本地磁盘(F) 本地磁盘(G) 本地磁盘(H) □丝竹坊 宁被培训班 中甜 中回本地磁盘() 中本地磁盘(K) 控制面板 网上邻居 回收站 e Internet Explorer 个对象可用磁盘空间:1,37GB) 259MB回我的电脑 圃开始‖圈多⊙四⊙的国甜国0國k树M多1陈慧琳:」些1651 2021/2/20

2021/2/20 5 运 筹 学 Operations Research （3）在计算机上，Windows操作系统采用树形结构管理文 件与目录系统

运筹学 Operations Research (4)化学物质的结构:同分异构体 H一C一C—一H 丙烷C3H8 2021/2/20 6

2021/2/20 6 运 筹 学 Operations Research （4）化学物质的结构：同分异构体

运筹学 Operations Research (5)家谱( family tree) 世世和(穆庄 升立 白(水牛 庄 手 I家家家 已m 中文”本 2021/2/20 7

2021/2/20 7 运 筹 学 Operations Research （5）家谱（family tree）：

运筹学 Operations research emma1任一非平凡树均至少有两个叶 证 - 注:非平凡树的最长路的起点和终点必为悬挂点 2021/2/20 8

2021/2/20 8 运 筹 学 Operations Research Lemma 1 任一非平凡树均至少有两个叶. 证： ▌ 注：非平凡树的最长路的起点和终点必为悬挂点

运筹学 Operations Research 7h1(1)7是树 (2)7无圈,且E=V-1 (3)7连通,且E=v-1 (4)的任两顶点之间恰有唯一一条路相连 (5)7连通,且去掉任一条边后即不连通 台>(6)7无圈,且在任两顶点之间添加一条边即得一个圈 注:树是极小连通图,极大无圈图 2021/2/20

2021/2/20 9 运 筹 学 Operations Research (6) . (5) (4) (3) 1 (2) 1 1 (1) 无圈，且在任两顶点之间添加一条边即得一个圈 连通，且去掉任一条边后即不连通 的任两顶点之间恰有唯一一条路相连 连通，且 无圈，且 是树 T T T T T Th T     = −  = −     注：树是极小连通图，极大无圈图. ▌

运筹学 Operations Research 例1一个树中度为2,3,4的顶点的个数分别为2,1, 3,其余顶点为叶,求叶的个数 解:设叶的个数为x,则v=x+2+1+3由图论第一定理有, 1·x+2×2+3×1+4×3=2(x+2+1+3-1)→x=9 例2一个树有20个顶点,其中有8个叶,其余顶点的度均不 大于3,求2,3度顶点的个数 解:6,6 支撑树( spanning tree):本身是树的支撑子图 支撑树T 2021/2/20 10

2021/2/20 10 运 筹 学 Operations Research 例1 一个树中度为2，3，4的顶点的个数分别为2，1， 3，其余顶点为叶，求叶的个数. 1 2 2 3 1 4 3 2( 2 1 3 1) 9 2 1 3.  +  +  +  = + + + −  = = + + + x x x 解：设叶的个数为x，则 x 由图论第一定理有， 例2 一个树有20个顶点，其中有8个叶，其余顶点的度均不 大于3，求2，3度顶点的个数. 解：6，6.▌ ▌ 支撑树（spanning tree）：本身是树的支撑子图