当前位置：文档之家 › 2019离散数学课件-无向树.ppt

2019离散数学课件-无向树.ppt

  • 格式：ppt
  • 大小：1.04 MB
  • 文档页数：29

下载文档原格式

  / 29

合集下载

离散数学 图论-树

离散数学 图论-树

中序遍历（次序：左－根－右) 前序遍历（次序：根－左－右) 后序遍历（次序：左－右－根) b 中序遍历: c b e d g f a I k h j 前序遍历: a b c d e f g h i k j 后序遍历: c e g f d b k i j h a
例：给定二叉树，写出三种访问 结点的序列
是否为根树
(a) (no)
(b) (no)
(c) (yes)
从树根到T的任意顶点v的通 路(路径)长度称为v的层数。 v5的层数为 层。
层数最大顶点的层数称为树 高．将平凡树也称为根树。 右图中树高为（ ）。
v1
v2 v3
v4 v8v5Fra bibliotekv6v7 v10
v9
在根树中，由于各有向边的方向是一 致的，所以画根树时可以省去各边上的所 有箭头，并将树根画在最上方．
等长码：0-000；1-001；2-010；3-011；4-100； 5-101；6-110；7-111. 总权值: W2=3*100=300
4、二叉树的周游（遍历）
二叉树的周游：对于一棵二叉树的每一个结点都访问一次且 仅一次的操作 1）做一条绕行整个二叉树的行走路线（不能穿过树枝） 2）按行走路线经过结点的位臵（左边、下边、右边） 得到周游的方法有三种： 中序遍历（路线经过结点下边时访问结点） 访问的次序：左子树－根－右子树 前序遍历（路线经过结点左边时访问结点） 访问的次序：根－左子树－右子树 后序遍历（路线经过结点右边时访问结点） 访问的次序：左子树－右子树－根
2、根树中顶点的关系
定义：设T为一棵非平凡的根树， v2 ∀vi,vj∈V(T),若vi可达vj,则称vi为 vj的祖先,vj为vi的后代； v4 v5 若vi邻接到vj(即<vi,vj>∈E(T)，称 vi为vj的父亲,而vj为vi的儿子 v8 若vj,vk的父亲相同，则称vj与vk是兄 弟

9.1-无向树

9.1-无向树
，T 是连通图。 如果T 中有回路，那么回路上任意一对结点之间有两
条基本通路，这与题设条件矛盾。所以，图是连通 的且无回路，是树。
二、无向树的性质（续）
定理9.2 设T=<V,E>为n（n2）阶树，则T中至少有2个叶结点。 证明： (思路) 关键是应用 |E|=|V|-1
练习
已知树T中有度数为4、3和2的分支结点各1个，其余 结点均为叶结点，求树T中叶结点的数目？ 解 设树T中叶结点的数目为x，则树T的结点数目为(x+3) 。
定理 9.1 对于树T=<V,E>，|V|=n，|E|=m，下列性质 成立且相互等价： ① T中无回路且边数m=n-1； ② T是连通图且边数m=n-1； ③ T中无回路，但在T的任何不相邻结点之间增加一 条边，就得到唯一的一条基本回路。 ④ T是连通图，但删去任何一条边后，所得到的图 不连通。 ⑤ T中每对结点之间有唯一的一条基本通路。
二、无向树的性质（续）
（4） 由性质③来推证性质④。
如果T 不是连通图，则存在两个结点vi和vj，在结点vi 和vj之间没有通路，如果增加边(vi, vj)，不产生回路 ，这与性质③矛盾，因此，T 是连通图。
因为T 中没有回路，所以删除任意一条边，所得到的 图必定不是连通图。
二、无向树的性质（续）
§9.1 无向树
一、基本概念 无向树（简称树）：连通且不含有回路的无向图，常
用T表示。 森林：每个连通分支都是树的无向图。 叶结点（简称叶）：在树T中，度数为1的结点。 内部结点（或分支结点，简称分支点）：在树T中，
度数大于1的结点。
树？ 森林？ 叶？ 内部结点？
二、无向树的性质
（3） 由性质②来推证性质③。 对结点数进行归纳。 当n = 2时，m = n 1 = 1，由T的连通性质，T没有回路。如果两个结点之

《离散数学》课件-第16章树

《离散数学》课件-第16章树
解：易见所求为该图的一棵最小生成树，如图所示 总造价为57
18
16.3 根树及其应用
19
定义（有向树）设D是有向图，如果D的基图是无向 树，则称D为有向树。
在有向树中最重要的是根树。 定义16.6（根树）一棵非平凡的有向树，如果恰有 一个顶点的入度为O，其余所有顶点的入度均为1,则称该 树为根树。 入度为0的顶点称为树根，入度为1出度为0的顶点称 为树叶，入度为1出度不为0的点称为内点，内点和树根统 称为分支点。 树根到一个顶点的有向通路的长度称为该顶点的层数。 层数最大顶点的层数称为树高。 平凡树也称为根树。
2
16.1 树及其性质
3
定义16.1（树和森林） 连通且无回路的无向图称为无向树，简称为树，常用
T表示树。 平凡图为树，称为平凡树。 非连通且每个连通分支是树的无向图称为森林。 T中度数为1的顶点（悬挂顶点）称为树叶，度数大于
1的顶点称为分支点。 称只有一个分支点，且分支点的度数为n-1的n（n≥3）
定义16.8（子树）设T为一棵根树，则其任一顶点v 及其后代导若将层数相同的顶点都 标定次序，则称T为有序树。
根据每个分支点的儿子数以及是否有序，可将根树 分成如下若干类：
定义（跟树分类）设T为一棵根树 （1）若T的每个分支点至多有r个儿子，则称T为r叉 树。又若r叉树是有序的，则称它为r叉有序树。 （2）若T的每个分支点恰好有r个儿子，则称T为r叉 正则树。又若r叉正则树是有序的，则称它为r叉正则有 序树。 （3）若T为r叉正则树，且每个树叶的层数均为树高， 则称T为r叉完全正则树。又若r叉完全正则树是有序的， 则称它为r叉完全正则有序树。
8
平均编码长度为：L = ∑ P( i )× l( i ) = 2.53bit i=1

离散数学——树ppt课件

离散数学——树ppt课件
11
无向树的性质
定理16.2 设T是n阶非平凡的无向树，则T中至少有两片树叶。
证明
设T有x片树叶，由握手定理及定理16.1可知，
2(n 1) d(vi ) x 2(n x)
由上式解出x≥2。
12
例16.1
例16.1 画出6阶所有非同构的无向树。
解答 设Ti是6阶无向树。 由定理16.1可知，Ti的边数mi＝5， 由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(Ti)≤5。 于是Ti的度数列必为以下情况之一。
(1) 1，1，1，1，1，5 (2) 1，1，1，1，2，4 (3) 1，1，1，1，3，3 (4) 1，1，1，2，2，3 (5) 1，1，2，2，2，2
(4)对应两棵非同构的树， 在一棵树中两个2度顶点相邻， 在另一棵树中不相邻， 其他情况均能画出一棵非同构 的树。
13
例16.1
人们常称只有一个分支点，且分支点的度数为n-1的 n(n≥3)阶无向树为星形图，称唯一的分支点为星心。
知，G-e已不是连通图， 所以，e为桥。
9
(5)(6)
如果G是连通的且G中任何边均为桥，则G中没有回路，但在任 何两个不同的顶点之间加一条新边，在所得图中得到唯一的 一个含新边的圈。
因为G中每条边均为桥，删掉任何边，将使G变成不连通图， 所以，G中没有回路，也即G中无圈。
又由于G连通，所以G为树，由(1) (2)可知，
u,v∈V，且u≠v，则u与v之间存在唯一的路径Г，
则Г∪(u,v)（(u,v)为加的新边）为G中的圈， 显然圈是唯一的。
10
(6)(1)
如果G中没有回路，但在任何两个不同的顶点之间加一条新边， 在所得图中得到唯一的一个含新边的圈，则G是树。

离散数学 课件 PPT 精品课程 考研 大学课程 数学一 第九章 树

离散数学 课件 PPT 精品课程 考研 大学课程 数学一 第九章 树

例 (2)为(1)的一棵生成树T,(3)为T的余树.
（1）
（2）
（3）
余树可能不连通，也可能含回路。
2019/1/30
11
定理9.3 任何连通图G至少存在一棵生成树. 推论1 设n阶无向连通图G有m条边,则 m≥n-1. 推论2 设n阶无向连通图G有m条边,T是G的生 成树,T'是T的余树,则T'中有m-n+1条边.
（1）
（2）
（3）
m=8,n=5
2019/1/30 12
a
d b
f
e
图中, 初级回路aed， bdf，cef.
c
这3个回路中每一 个回路都只含一条 弦,其余的边都是树 枝,这样的回路称为 基本回路.
2019/1/30
13
定义9.3 设T是n阶连通图G=<V,E>的一棵生成 树,G有n条边.设e1,e2· · · ,em-n+1为T的弦,设Cr是T 加弦er产生的G的回路,r=1,2,…m-n+1.称Cr为 对应于弦er的基本回路,称{C1,C2,· · · ,Cm-n+1}为 对应生成树T的基本回路系统.
连通分支数大于等于2,且每个连通分支均
平凡图称为平凡树. 设T＝<V,E>为一棵无向树,v∈V,若d(v)＝1,
则称v为T的树叶.若d(v)≥2,则称v为T的分 支点.
2019/1/30 3
例
（a）
（b）
（c ）
图中（a），（b）为树，而（c）不是树， 但（c）为森林。
2019/1/30 4
T有5个树枝a, b, c, d, e, 因而有5个 基本割集:Sa={a,g,f } ; Sb={b,g,h } ; Sc={c,f,h } ; Sd={d,i,h } ; Se={e,f,i}. 基本割集系统为{Sa,Sb,Sc, Sd,Se}.

离散数学课件 第七章 树trees

离散数学课件 第七章 树trees

第7章树trees分类§7.1 树定义1：T是集合A上一个二元关系，T称为树tree，如果存在v0∈A，任意v∈A，v≠v0，到v0都有唯一一条路径，（v0, v0） T. T叫做根树，记做（T，v0）。

A中元素称为T的顶点vertex，T中元素称为边，v0称为根root。

定理1. 设（T，v0）是树，则(a)T中没有回路。

(b)只有一个根v0。

(c)任意v∈A，v≠v0，v有入度1，v0入度是0。

证明：定义2层次levelv0的层次为0，v0的子女offspring层次为1，v0是子女的父母parent。

v i的层次为k，v i的子女offspring层次为k ＋1，v i是子女的父母parent，T的最大层次称为高度height。

无子女的顶点叫叶leaf。

v i的子女叫同胞sibling，同胞如有长幼，从左到右，老大，老二，老三等，组成线性序，T称为有序树，ordered tree定理2. 设（T，v0）是根树，则(a)T反自反。

(b)T反对称。

(c)(a,b)∈T，(b，c)∈T ⇒ (a，c)∉T。

定义3：n－树：每个顶点至多n个子女。

二叉树：2－树。

完全n－树：每个非叶顶点恰有n个子女。

定义4A rooted binary tree is a rooted tree in which every node has at most two children.A full binary tree (sometimes proper binary tree or 2-tree) is a tree in whichevery node other than the leaves has two children.A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.[1] (This is ambiguously also called a complete binary tree.)A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.[2]An infinite complete binary tree is a tree with levels, where for each level d thenumber of existing nodes at level d is equal to 2d. The cardinal number of the set of all nodes is . The cardinal number of the setof all paths is .A balanced binary tree is a tree where the depth of all the sub-trees differs by at most 1.定理3. 设（T，v0）是根树，v∈T，则T(v)是T的子树，T(v)的根是v。

离散数学-树

离散数学-树
该n元有序树又称n元位置树。2元位置树各分支结点 的左右儿子分别称为左儿子和右儿子。
离散数学导论
. 树
1.2 生成树
➢定义9.10
图T称为无向图G的生成树（spanning tree）， 如果T为G的生成子图且T为树。
✓定理9.17
任一连通图G都至少有一棵生成。
.. 树树
1.2 生成树
✓ 定理9.18
设G为连通无 向图，那么G的 任一回路与任一生 成树T的关于G的补 G – T ，至少有一 条公共边。
1.3 根树
➢ 定义9.15
每个结点都至多有两个儿子的根树称为 二元树（quasibinary tree）。类似地，每个结点都
至多有n个儿子的根树称为n元树。 对各分支结点 的诸儿子规定了次序（例如左兄右弟）的n 元树称
为n元有序树；若对各分支结点的已排序的诸儿子
规定了在图示中的位置（例如左、中、右），那么
弦组成G的一个割集，它被称为枝t-割集（t-cut set）；
而每一条弦e与T中的通路构成一回路，它被称为弦e-回
路（e-circuit）。
. 树
1.2 生成树
✓ 定理9.20
在连通无向图G中，任一回路与任 一割集均有偶数条公共边。
. 树
1.2 生成树
✓ 定理9.21
设G为一连通无向图，T是G的生成树， S = {e1, e2, e3,…,ek}
✓ 定理9.19
设G为连通无 向图，那么G的任 一割集
与任一生成树至少
有一条公共边。
.. 树树
1.2 生成树
➢ 定义9.11
设T为图G的生成树，称T中的边为树枝（branch） 称G – T 中的边为弦（chord）。对每一树枝t，T–t分为

《离散数学》课件-第九章 树(A)

《离散数学》课件-第九章 树(A)
• 证明 除根之外的每个结点都是分支点的儿子。因 为每个分支点都有m个儿子，所以，在树中除根之 外还有mi个结点。因此，这棵树共有mi+1个结点。
定理9.3.2
• 定理9.3.2一个m元正则树T 1. 若T有n个结点，则有i=（n−1）/m个分支点和 l=[(m−1)n+1]/m片树叶； 2. 若T有i个分支点，则有n=mi+1个结点和l=(m−1)i+1片树叶； 3. 若T有l片树叶，则有n=(ml−1)/(m−1)个结点和i=（l−1） /(m−1)个分支点。
大于等于2，则 2e deg(v) 2k ，从而ek,，即图T至少有k条边，与e= vV
n-1矛盾。在T中删去1度结点v0及其关联的边，得到新图T也是连通的。 根据归纳假设，T无回路，e= n-1，将删去的1度结点v0及其关联的边添 入T得到图T ，T中仍无回路，且e= n-1。
➢ （4）（5）。用反证法证明。假设在T的每一对结点之间的简单路不唯
T1
T2
T3
9
生成树
• 定义9.2.1 给定连通图G,如果它的生成子图TG是树,则称TG为G的生成树。生 成树TG中的边称为树枝；G中的不在TG中的边称为弦；TG的所有弦的集合 称为生成树TG的余树。 例如 图中黑边构成生成树 红边构成余树
注意: 余树一般不是树
10
例题
• 例9.2.1 在图9.2a.1中，哪e 些是图9a.2.1(1e)的生成树a？ e
• 证明 用归纳法对高度h进行归纳证明。
• 假设高度h=1。高度h=1的m元树由根结点及其不超过m个子 结点组成，每个子结点都是树叶。因此高度为h的m元树里至 多有m1=m片树叶。
• 因此，数据集D上的k聚类就是求使得 D( ) 最大的k划分。

离散数学课件-无向树

离散数学课件-无向树

12
(5) (6)的证明
如果G连通且每条边均为桥，则G中任意两个结点之间存在 惟一的路径。 证明 由G是连通的可知，任意两个结点间有一条路， 若存在两点它们之间有多于一条的路， 则G中必有回路， 删去该回路上任一边， 图仍是连通的， 与G中每条边都是桥矛盾。
13
(6) (1)的证明
如果G中任意两个结点之间存在惟一的路径，则G是无回路 的连通图。 证明 因为任意两结点间有唯一条路，则图G必连通。 若G有回路， 则在回路上任意两结点间有两条路， 与已知矛盾。
6 b 5
删除边6
a
2 (c)
e
最小生成树
对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作赋权图, 记作G=<V,E,W>. 设G是G的子图, G所有边的权的和称作G的权, 记作W(G).
最小生成树: 赋权图的权最小的生成树
求最小生成树的算法——避圈法 (克鲁斯卡尔/Kruskal算法) 设G=<V,E,W>, 将非环边按权从小到大排序：e1, e2, …, em. (1) 把e1加入T中 (2) 检查e2, 若e2与e1不构成回路, 则将e2加入T中, 否则弃去e2. (3) 检查e3,…, 重复进行直至得到生成树为止.
11
(4) (5)的证明
如果G中无回路, 但增加一条新边，得到一个且仅有一个包含 新边的回路，则G连通且每条边均为桥。 证明 反证法。 假设G不连通， 则存在结点ui与uj，在ui和uj之间没有路， 所以增加边(ui,uj)不会产生回路，与已知矛盾。 由于G无回路，故删掉任意条边e都使G-e为非连通， 所以G中每条边都是桥。
从连通图从连通图ggee中的某一顶点中的某一顶点uu出出发选择与它关联的具有最小权值的边发选择与它关联的具有最小权值的边uu00vv将其顶点加入到将其顶点加入到生成树的顶点集合生成树的顶点集合uu中

离散数学——树ppt课件

离散数学——树ppt课件
4
(1)(2)
如果G是树，则G中任意两个顶点之间存在唯一的路径。
存在性。 由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到 vj(vivj)存在通路，则vi到vj 一定存在长度小于等于n-1的初级 通路(路径)）可知，
u,v∈V，u与v之间存在路径。
唯一性（反证法）。 若路径不是唯一的，设Г1与Г2都是u到v的路径， 易知必存在由Г1和Г2上的边构成的回路， 这与G中无回路矛盾。
ij，i, j互不为前缀，则称A为前缀码。
若i(i=1,2,…,m)中只出现0与1两个符号，则称A为二元前缀码。 (2)如何产生二元前缀码？ 定理16.6 由一棵给定的2叉正则树，可以产生唯一的一个二元前缀
码。
35
方法：
将每个分支点引出的两条边分别标上0和1。
结果：
图所示树产生的前缀码为{00, 10, 11, 011, 0100, 0101}。
r叉完全正则有序树——r叉完全正则树是有序的
30
最优二叉树
定义16.9 设2叉树T有t片树叶v1, v2, …, vt，权分别为w1, w2,
t
…, wt，称 W (t) wil(vi ) 为T的权，其中l(vi)是vi的层数， i 1
在所有有t片树叶、带权w1, w2, …, wt的2叉树中，权最小的 2叉树称为最优2叉树。
1，1，1，2，2，2，3
由度数列可知，Ti中有一个3度顶点vi，vi的邻域N(vi)中有3个 顶点，这3个顶点的度数列只能为以下三种情况之一：
1,1,2
1,2,2
2,2,2
设它们对应的树分别为T1，T2，T3。此度数列只能产生这三棵 非同构的7阶无向树。
15
例16.2

离散数学(第二版)第9章树

离散数学(第二版)第9章树

e10， 则分别产生初级回路e1e3e4， e1e4e5e2， e6e8e9，
•
•
•
e7e6e9e10。
•
第九章 树
这些初级回路有一个共同特点： 它们中均只含一条弦，
其余的边均是树枝， 我们称这样的回路为基本回路。 对于
G的每棵生成树T， m-n+1条弦对应着m-n+1个基本回路，
这些基本回路构成的集合称为对应T的基本回路系统。 显
例如图9.1.3中， T1和T2是图G的两棵生成树， 1 和2 是 分别对应于它们的余树。
第九章 树
图9.1.3 图的生成树和余树
第九章 树
由图9.1.3可见， G与T1、 T2的区别是G中有回路， 而 它的生成树中无回路， 因此要在一个连通图G中找到一棵 生成树， 只要不断地从G的回路上删去一条边， 最后所得 无回路的子图就是G的一棵生成树。 于是有如下定理。
这个问题的数学模型为： 在已知的带权图上求权最小 的生成树。
定义9.1.4 设无向连通带权图G=〈V, E, ω〉， G中带 权最小的生成树称为G的最小生成树(最优树)。
定理9.1.4 设连通图G的各边的权均不相同， 则回路 中权最大的边必不在G的最小生成树中。
证明略。
第九章 树
定理的结论是显然的， 由此寻找带权图G的最小生成 树， 可以采用破圈法， 即在图G中不断去掉回路中权最大 的边。
(5) 1， 1， 1， 1， 1， 2， 5
(6) 1， 1， 1， 1， 1， 3， 4
(7) 1， 1， 1， 1， 1， 1， 6
第九章 树
注意到， 不同构的度数列对应不同的树， 但对应同一 度数列的非同构的树不一定唯一， 所以对应(1)有T1， 对应 (2)有T2、 T3和T4， 对应(3)有T5和T6， 对应(4)有T7和T8， 对应(5)有T9， 对应(6)有T10， 对应(7)有T11(见图9.1.2)。

第二十七讲--无向树

第二十七讲--无向树

图 8.6―3
4
二、生成树
下面研究图G关于给定生成树T的基本回路系统与基本割集系统 之间的关系。
二、生成树
定理7：设 D={e1,e2,e3,…,ek}是一个基本割集,其 中 e1 是树枝 ,e2,e3,…,ek是生成树的弦。则 e1包 含在对应于ei(i=2,3,…,k)的基本回路中,而不包 含在任何其它的基本回路中。 举一例,以加深对定理的理解。如图8.6―4 所示,生成树是{a,b,e,h,i},其中一枝为e,包含e的 割集为{e,d,f},则由弦d决定的基本回路{a,b,e,d} 和由弦f决定的基本回路{e,h,i,f}都含有e,而其余 两个基本回路都不含e。
5. 设G=<V,E>是无向图, 若存在边子集 E`⊂E ，使得图G删除E`后所得子图 二、生成树 G-E`的连通分支数W(G- E`)>W(G)； 而删除E`的任一真子集E“后所得子图G-E”的连通分支数W(GE“)=W(G), 则称E`为G的一个边割集。 若G的一个边割集中只含有一条边，则称该边为割边。
第二十七讲
讲授内容：
树
第二十七讲
树
1.无向树
无向树，森林 树的等价定义 基本结论
2.生成树
生成树 基本回路 基本割集 基本回路与基本割集的关系
讲授重点：树基本概念，等价定义，最小生成树 讲授难点：基本回路与基本割集的关系
3.最小生成树及其求解算法
取小法 去大法
一、无向树
1.无向树：连通而无简单回路的无向图称为无向树,简称树(tree)
图 8.6―1 例如图8.6―1(a)、(b)所示的都是树,(c)所示的是森林。
一、无向树
证明：轮转法
一、无向树 证明： 1) 树的定义 连通而无简单回路
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

10
(3)(4)的证明
首先证明G中也无回路 删去u0及其关联的边，得到含有k-1个结点的图G’， G’连通且m’=n’1。由归纳假设知G’无回路。 在G’中加入u0及其关联的边恢复到G，则G无回路。 再证明在G中任意两结点之间增加一条边，得到一条且仅有一条回路。 若在G中增加一条边(ui,uj)， 因为G连通，则在G中存在一条从ui到uj的路， 那么这条路与新加入的边(ui,uj)构成回路， 而且这个回路是唯一的。 若不唯一，删掉边(ui,uj)边,G中必有回路，矛盾。
9
(3)(4)的证明
如果G连通且m=n1，则G中无回路, 但增加一条新边，得到 一个且仅有一个包含新边的回路。 证明 归纳法。 当n=2时，m=n-1=1，必无回路，如果增加一边得到且仅得 到一个回路。 设n=k-1时命题成立。考察n=k时的情况。 因为G是连通的，所以每个结点u有deg(u)≥1， 下面证明至少有一个结点u0使deg(u0)=1。 若不存在，则每个结点的度至少为2，所以2n≥2m，即n ≥m， 这与m=n-1矛盾。
的连通无向图G’，
7
(1)(2)的证明（续）
由归纳假设可知， G’的边数m’=n’-1=(k-1)-1=k-2。
再将结点u及(u,w)放入原位，恢复到图G，
那么G的边数 m=m’+1=(k-2)+1=k-1， 结点数n=n’+1=k， 故m=n-1成立。
8
(2)(3)的证明
如果G中无回路且m=n1，其中m是边数，n是结点数，则连 通且m=n1; 只须证明G是连通的。 证明 设G有k个连通分枝G1,…,Gk(k≥1），Gi有ni个结 点,mi条边，因为Gi连通无回路，所以有 mi =ni-1，n=n1+n2+…+nk m=m1+m2+…+mk=(n1-1)+(n2-1)+…+(nk-1)=n-k 因为m=n-1，所以k=1，故G是连通的。
离散数学 离散数学
李书杰 合肥工业大学 lisjhfut@
1
学习内容
10.1 无向树 10.2 根树
2
张怡宁 － 0
张怡宁 （中国）
帖雅娜 （香港） 李佳薇 (新加坡)
4－ 0
李佳薇 (新加坡)
3－ 4
3
如果将上图看作一个图的话，这个图就是一棵树，如下图。
解 用树的性质m=n1和握手定理. 设有x片树叶，于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=13+22+x 解出x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向树, 如图所示
16
例题
例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的 度数均为4. 求T的阶数n. 解 设T的阶数为n, 则边数为n1, 4度顶点的个数为n7. 由握 手定理得 2m=2(n1)=51+21+31+4(n7) 解出n=8, 4度顶点为1个. T的度数列为1,1,1,1,1,2,3,4
12
(5) (6)的证明
如果G连通且每条边均为桥，则G中任意两个结点之间存在 惟一的路径。 证明 由G是连通的可知，任意两个结点间有一条路， 若存在两点它们之间有多于一条的路， 则G中必有回路， 删去该回路上任一边， 图仍是连通的， 与G中每条边都是桥矛盾。
13
(6) (1)的证明
如果G中任意两个结点之间存在惟一的路径，则G是无回路 的连通图。 证明 因为任意两结点间有唯一条路，则图G必连通。 若G有回路， 则在回路上任意两结点间有两条路， 与已知矛盾。
6
(1)(2)的证明
如果G是无回路的连通图，则G中无回路且m=n1，其中m是 边数，n是结点数 证明 归纳法。 当n=2时，因为G连通无回路， 所以只有m=1，故m=n-1成立。
假设n=k-1时命题成立，当n=k时，
因G是无回路且连通，则至少有一个度为1的结点u， 设与其关联的边为(u,w)，删去u，得到一个k-1个结点
14
无向树的性质(续)
定理10.2.2 设T 是n阶非平凡的无向树，则T中至少有两片树叶. 证 设T有x片树叶，m条边。由握手定理及定理10.2.1可知，
m n 1 2m d (vi ) x 2(n x)
由上式解出x2.
15
例题
例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全 是树叶. 试求树叶数, 并画出满足要求的非同构的无向树.
n4 n5 n6 n7 n3 n1 n2
n7
n6
n5
n4
n1
n3
n2
n2
n3
n1
n4
n5
n6
n7
4
定义10.2.1 无向树－－从无向图出发定义的树




无向树(树): 连通而无回路的无向图，一般用T＝<V,E>表示 叶: 树中度数为1的顶点 分支点/内部结点: 树中度数>1的顶点 森林: 一个非连通图，如果其每个连通分支都是树，则称为 森林 平凡树: 平凡图，只有一个点且无边的图 右图为一棵12阶树. 声明:本章中所讨论的回路均 指简单回路或初级回路
17
定义10.2.2
生成树 设G为无向连通图，若G的生成子图（v’=v）是一棵树 ,
则称这棵树为G的生成树； 设G的一棵生成树为 T, 则T中的边称为 T的树枝,在G中而 不在T中的边称为T的弦, 所有弦的集合称为生成树T的补 注意：生成树 T的补不一定连通, 也不一定不含回路. T 右图黑边构成生成树 红边构成补
5
无向树的性质
定理10.2.1 设G=<V,E>是n阶m条边的无向图，则下面各命题 是等价的： （1）G是树(连通无回路); （2）G中无回路且m=n1; （3）G是连通的且m=n1; （4）G中没有回路, 但在任何两个不同的顶点之间加一条新 边,就会得到一条唯一的基本回路. （5）G是连通的且G中任何边均为桥; （6） G中任意两个顶点之间存在惟一的 一条基本通路。
11
(4) (5)的证明
如果G中无回路, 但增加一条新边，得到一个且仅有一个包含 新边的回路，则G连通且每条边均为桥。 证明 反证法。 假设G不连通， 则存在结点ui与uj，在ui和uj之间没有路， 所以增加边(ui,uj)不会产生回路，与已知矛盾。 由于G无回路，故删掉任意条边e都使G-e为非连通， 所以G中每条边都是桥。