第六章 图.ppt

第六章图
Review
哈夫曼算法
哈夫曼编码
练****br/>假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,(要求树中左孩子结点的权值小于右孩子的权值),分别写出每个字母的哈夫曼编码。
图的定义
图是由非空的顶点集合和描述顶点之间关系的集合组成
G =( V ,E ) V = { vi | vi∈VertexType} E= { <vi,vj> | vi,vj ∈V∧P(vi,vj)}
P(vi,vj)的含义是:
有向图——<vi,vj> 无向图——(vi,vj)
图的定义
[] 有一个图G1=( V1 , E1 ),其中:
V1 = { 0 , 1 , 2 , 3 , 4 } E1 = { (0,1),(1,2),(2,3),(3,4),(2,4),(0,3)}有另一个图G2=( V2 , E2 ),其中: V2 = { 0 , 1 , 2 , 3 , 4 } E2 = { <0,1>,<1,2>,<2,4>,<0,4>,<4,3>,<3,2>}画出这两个图的逻辑结构
0
1
2
4
3
0
1
2
3
4
图的基本术语
无向图和有向图
无向完全图和有向完全图
图的基本术语
子图
设有两个图G=(V,E)和G'=(V',E'),若V'是V的子集,即V' V ,且E'是E的子集,即E' E,则称G'是G的子图
图的基本术语
连通、连通图和连通分量
A
B
L
M
C
F
D
E
J
G
H
K
I
图a 无向图G
A
B
L
M
C
F
J
D
E
G
H
K
I
图b 无向图G的连通分量
图的基本术语
强连通图和强连通分量
0
1
2
3
4
0
1
2
3
4
图b 有向图G的强连通分量
[]如果图G1是一个具有n个顶点的连通无向图,那么G1最多有多少条边?G1最少有多少条边?如果图G2是一个具有n个顶点的强连通有向图,那么G2最多有多少条边?G2最少有多少条边?
解:G1为完全无向图时边最多,即G1最多有n(n-1)/2条边,G1最少n-1条边。
G2为完全有向图时边最多,即G2最多有n(n-1)条边,G2最少有n条边。
0
1
2
4
3
0
1
2
3
4
图的基本术语