9.1 无向树及生成树.docx

第二次课
授课时间第十七周
授课章节

教学方法
板书和电子课件结合
任课教师
唐新华
与手段
及职称
讲师
课时安排
2课时
1、教材：
使用教材和
主第二次课
授课时间第十七周
授课章节

教学方法
板书和电子课件结合
任课教师
唐新华
与手段
及职称
讲师
课时安排
2课时
1、教材：
使用教材和
主要参考书
耿素云等，离散数学，清华大学出版社，2008
参考书
左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006
教学与目的要求:掌握树、生成树的概念以及图是树的几个等价命题
教学重点、难点:
重点：树及其性质、无向树的等价定义与性质、生成树、最小生成树难点：生成树存在条件、基本割集与基本割集系统
教学内容:

一、本节主要内容
无向树、森林树枝、弦、余树生成树
基本回路与基本回路系统基本割集与基本割集系统最小生成树
二、教学内容
无向树
无向树（树）：连通而无回路的无向图，：平凡图
森林：每个连通分支都是树的非连通的无向图树叶：树中度数为1的顶点分支点：树中度数2的顶点
右图为一棵12阶树.
声明:本章中所讨论的回路均
指简单回路或初级回路
无向树的性质
=vV,E>是n阶m条边的无向图，则下面各命题是等价的：
（1）G是树（连通无回路）；
（2）G中任意两个顶点之间存在惟一的路径；
（3）G中无回路且m=n-1;
（4）G是连通的且m=n-1;
（5）G是连通的且G中任何边均为桥；
（6）G中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.
无向树的性质（续）
例题
例1已知无向树T中，有1个3度顶点,2个2度顶点，其余顶点全是树叶•试求树叶数,
「I>
IIo（I
并画出满足要求的非同构的无向树.
解用树的性质m=n-1和握手定理.
设有x片树叶，于是n=1+2+x=3+x,
2m=2（n-1）=2x（2+x）=1x3+2x2+x
解出x=3，故T有3片树叶.
T的度数列为1,1,1,2,2,3
有2棵非同构的无向树，如图所示
例题
例2已知无向树T有5片树叶,2度与3度顶点各1个，,并画出满足要求的所有非同构的无向树.
解设T的阶数为n,则边数为n-1,4度顶点的个数为n-
2m=2（n-1）=5x1+2x1+3x1+4（n-7）
解出n=8,4度顶点为1个.
T的度数列为1,1,1,1,123,4
有3棵非同构的无向树
生成树
生成树的存在性
定理任何无向连通图都有生成树.
，，这不破坏连通性，重复进行
直到无圈为止，剩下的图是一棵生成树.
推论1设n阶无向连通图有m条边，则m>n-1.
推论2设n阶无向连通图有m条边，则它的生成树的余树有m-n+1条边.
基本回路与基本回路系统
定义设T是n阶m条边的无