文档介绍：会计学
1
数据结构(shù jù jié ɡòu)图
第一页，共104页。
2
哥尼斯堡七桥问题 德国古城—哥尼斯堡—普雷格尔河—七
桥问题：从任一桥头出发，依次(yīcì)走过每座
桥，每座桥只走一次，最后回到出发点。
——一笔画问题
第1页/共104页
第二页，共104页。
3
第2页/共104页
第三页，共104页。
4
第3页/共104页
第四页，共104页。
5
基本术语
存储结构(jiégòu)
图的遍历
图的连通性
图的应用
第7章 图
第4页/共104页
第五页，共104页。
6
图的基本(jīběn)术语
其中：V 是G 的顶点集合(jíhé)，是有穷非空集；
E 是G 的边集合(jíhé)，是有穷集。
问：当E(G)为空时，图G存在否？
答：还存在！但此时图G只有(zhǐyǒu)顶点而没有边。
有向图：
无向图：
完全图：
图G中的每条边都是有方向的；
图G中的每条边都是无方向的；
图G任意两个顶点都有一条边相连接；
若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图
若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图
V=vertex
E=edge
图：记为 G＝( V, E )
v1
v2
v3
v5
v4
v4
v1
v2
v3
v4
有向边(u, v)称为弧，边的始点u 叫弧尾，终点v 叫弧头。
第5页/共104页
第六页，共104页。
7
例：判断下列4种图形(túxíng)各属什么类型？
无向(wú xiànɡ)
无向(wú xiànɡ)图(树)
有向图
有向
n(n-1)/2 条边
n(n-1) 条边
G1的顶点集合为V(G1)={0,1,2,3}
边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
完全图
完全图
第6页/共104页
第七页，共104页。
8
证明(zhèngmíng)：
证明：若是完全有向图，则n个顶点中的每个顶点都有一条(yī tiáo)弧指向其它n-1个顶点, 因此总边数=n(n-1)
证明：从①可以直接推论出无向完全图的边数——因为无方向(fāngxiàng)，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。
② 完全无向图有n(n-1)/2 条边。
① 完全有向图有n(n-1)条边。
1
2
3
4
1
2
3
4
第7页/共104页
第八页，共104页。
9
稀疏(xīshū)图： 稠密图：
设有两个(liǎnɡ ɡè)图 G＝(V, E) 和 G’＝(V’, E’)。若 V’ V 且 E’ E, 则称 图G’ 是 图G 的子图。
子 图：
边较少的图。通常(tōngcháng)边数远少于nlogn
边很多的图。
无向图中，边数接近n(n-1)/2
有向图中，边数接近n(n-1)
第8页/共104页
第九页，共104页。
10
带权图：
即边上带权的图。其中权是指每条边可以标上具有(jùyǒu)某种含义的数值（即与边相关的数）。
连通(liántōng)图：
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。
非连通图的极大(jí dà)连通子图叫做连通分量。
→带权图
在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。
强连通图：
网 ：
D
E
A
B
C
F
J
L
M
G
H
I
K
非强连通图的极大强连通子图叫做强连通分量。
第9页/共104页
第十页，共104页。