离散数学图论

问题1 最短路径问题
如下带权的有向图G=(V，E)中，求从结点0
到其余各结点的短路径和路径长度，其中结点0
称为源点。
70
0 50 1 10 4
15
35
20 10
20
30
2 15 3 3 5
1
下表列出了有向图中从结点0到其余各结点的 最短路径和路径长度。
源点 0
终点 1 2 3 4 5
最短路径 (0,2,3,1)
34
（33）有向图的邻接矩阵
定义 设有向图D=<V, E>, V={v1, v2, …, vn}, E={e1,
e2,
…,
em},
令
a(1) ij
为顶点vi邻接到顶点vj边的条数，
称(
a(1) ij
)nn为D的邻接矩阵,
记作A(D),
简记为A。
性质： ——P289
例19 如右图：
0 1 0 0
A
0 0 1 1 0 0 0 0
（22）通路与回路的性质 P281-P22 定理14.5及推论、定理14.6及推论
19
说明:
• 还可以用更简单的表示法表示通路和回路：
① 只用边的序列，如 =e1e2…el ② 简单图中，用顶点的序列，如 =v0v1…vl
③非简单图中,可用混合表示法,
如 =v0v1e2v2e5v3v4v5
• 环是长度为1的圈, 两条平行边构成长度为2的圈。 • 简单无向图中，圈的长度3；在有向简单图中, 所
D的最大出度+(D), 最小出度+(D) 最大入度 (D), 最小入度 (D) 最大度(D), 最小度(D)
例6 如右图， d+(a)=4, d(a)=1, d(a)=5, d+(b)=0, d(b)=3, d(b)=3,
+(D)=4, +(D)=0, (D)=3, (D)=1, (D)=5, (D)=3.
12
（13）握手定理
定理 任意无向图和有向图的所有顶点度数之和都
等于边数的2倍, 并且有向图的所有顶点入度之 和等于出度之和等于边数.
d(v) 2m d(v) d(v) m
推论 在任何无向图和有向图中，奇度顶点的个数必
为偶数.
例7 下列各图中各有多少个顶点？
(1) 16条边，每个顶点的度数均为2。
(2) 21条边, 3个4度的顶点, 其余顶点的度数均为3。
(3) 24条边，每个顶点的度数均相同。
13
（14）图的度数列
设无向图G的顶点集V={v1, …, vn} G的度数列: d(v1), d(v2), …, d(vn)
如右图度数列:4,4,2,1,3
设有向图D的顶点集V={v1, v2, …, vn} D的度数列: d(v1), d(v2), …, d(vn) D的出度列: d+(v1), …, d+(vn) D的入度列: d(v1), …, d(vn)
（6）顶点和边的关联
关联、关联次数、环、孤立点
（7）相邻
vi
vj
点相邻、边相邻
(vi,vj)
ek el
8
（8）邻接
vi
邻接到、邻接于
（9）邻域和关联集
设无向图G, vV(G)
v的邻域、 v的闭邻域、 v的关联集
设有向图D, vV(D)
v的后继元集
v的先驱元集
先
v
v的邻域
驱
v的闭邻域
vj
后 继
9
（10）多Hale Waihona Puke Baidu图 平行边、重数
(0,2) (0,2,3) (0,2,3,1,4)
—
路径长度 45 10 25 55 ∞
2
问题2 旅行商问题
下图是连通无向图G=(V，E)，求图的所有 Hamilton回路。
0
12
3
56 7 8
9
10
3
第十四章 图的基本概念 第十五章 欧拉图与哈密顿图
主要知识内容
4
本章知识点的 关联图：
5
14.1 图
d(v1)=4, (G)=4, (G)=1,
v4是悬挂顶点, e7是悬挂边, e1是环。
11
设D=<V,E>为有向图, vV, v的出度d+(v)：v作为边的始点次数之和 v的入度d(v)：v作为边的终点次数之和 v的度数(度) d(v)：v作为边的端点次数之和 d(v)= d+(v)+ d-(v)
例10 画出K4的所有非同构的生成子图。
（20）补图、自补图
图的运算： 记 Gv：从G中删除v及关联的边
GV：从G中删除V中所有的顶点及关联的边 Ge：从G中删除e GE：从G中删除E中所有边
18
14.2 通路与回路
（21）通路与回路 通路、起点和终点、长度、回路 简单通路、简单回路 初级通路(路径)、初级回路(圈) 奇(偶)圈
1 1 0 0
v1 e2
v4
e1 e3 e4
v2 e5 v3
35
（34）D中的通路及回路数
定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中
元素，
a(l ij
)
为D中vi到vj长度为
l
的通路数，
a(l ii
)为vi到自身长度为
l
的回路数，
nn
a( l ) ij
为D中长度为
l
的通路总数，
i1 j1
注意：图的数学定义与图形表示，在同构的意义 下是一一对应的。
7
（5）几个特殊的图
通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用ek表示无向边或有向边. V(G), E(G) —表示图G的顶点集, 边集.
|V(G)|, |E(G)| —表示图G的顶点数集（阶）和边数.
n 阶图、有限图、零图、平凡图、空图、基图
(1) d= (5,3,3,2,1) (2) d= (3,2,1) (3) d= (3,3,2,1)
15
（16）图的同构
例11 试画出4阶3条边的所有非同构的无向简单图 例12 判断下述每一对图是否同构。
a
b
c
16
d
e
（17）完全图 n阶无向完全图Kn、n阶有向完全图
（18）n阶k正则图
17
（19）子图 子图、母图 、生成子图、真子图 V 的导出子图、 E 的导出子图
27
定理(强连通判别法) D强连通当且仅当D中存在经 过每个顶点至少一次的回路。
定理(单向连通判别法) D单向连通当且仅当D中存 在经过每个顶点至少一次的通路。
例15 判断以下有向图的连通性。
v1
v1
v1
v1
v1
v2 v3 v2 v3 v2 v3 v2 v3 v2 v3
(1)
(2)
(3)
(4)
(5)
例11 如右图，写出所 v1
有的点割集和割点。
例12 如下图，写 出所有的点割集 和割点。
v2 v4
v3
v5
v7 v6
24
（26）边割集 定义： 边割集 割边（桥）
例13 写出例11和例12的所有边割集和桥。
几点说明： ① Kn无点割集 ② n阶零图既无点割集，也无边割集. ③ 若G连通，E为边割集，则p(GE)=2 ④ 若G连通，V为点割集，则p(GV)2
（11）简单图 例4 判别下图是否是简单图？
10
（12）顶点的度数 设G=<V, E>为无向图, vV,
v的度数(度) d(v)：v作为边的端点次数之和 悬挂顶点：度数为1的顶点 悬挂边：与悬挂顶点关联的边
G的最大度(G)=max{d(v)| vV} G的最小度(G)=min{d(v)| vV}
例5 如右图， d(v5)=3, d(v2)=4,
32
14.4 图的矩阵表示
（31）无向图的关联矩阵
无向图G的关联矩阵，记为M(G)，表示点与边的 关联次数。
性质：——P288
例17 如右图：
e1 e2 e3 e4 e5
v1 2 1 1 1 0
M
(G)
vv23
v4
0 0 0
1 0 0
1 0 0
0 1 0
0 1 1
e1
v1
v4
e2
e4 e3
e5
v2 v3
G
26
（28）有向图的连通性
设有向图D=<V, E> ， vi, vj V vi可达vj：若vi 到vj 存在通路。记vi vj 。
规定 自身可达，即vi vi 。 vi与vj相互可达，记vi vj 。规定 vi vi 说明： 是V上的等价关系。 D弱连通(连通)：D的基图为无向连通图 D单向连通： vi vj或vj vi 至少成立起一 D强连通： vi, vj V，均有vi vj 强连通单向连通弱连通
如右图度数列:5,3,3,3 出度列：4,0,2,1 入度列：1,3,1,2
14
（15）可图化、可简单图化
n
定理：可图化 di 为偶数。 i 1
定理：可简单图化，则△(G) ≤n-1。—充分条件
例8 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗? 例9 已知图G有10条边，4个3度顶点，其余顶点 的度数均小于2，问G至少有多少个顶点? 例10 根据度数列，画图.
6
一般地，用小圆圈（或实心点）表示顶点，用 顶点间的连线表示无向边，用有方向的连线表示 有向边。如
u
vu
v
(u, v)
(起点) <u, v> (终点)
例3 设D=<V, E>，V={a, b, c, d, e}，E={<a, a>, <a, b>, <a, b>, <b, a>, <b, c>, <c, d>, <d, b>}，画图。
33
（32）有向图的关联矩阵
定义 M(D)=(mij)nm
性质：——P288
1 , mij 0 ，
vi为e
的
j
始
点
vi与e
不
j
关
联
1，
vi为e
的
j
终
点
例18 如下图：
v1 e2
v4
e1 e3 e4
v2 e5 v3
1 1 0 0 0
M(D)
1 0
0 0
1 0
1 1 0 1
0 1 1 1 0
25
（27）点(边)连通度 点连通度：κ(G)=min{|V| | V为G的点割集} 边连通度：λ(G)=min{|E| | E为G的边割集}
如例11中， κ(G)=1， λ(G)=2。
例14 如右图G，是1-连通图， k边-连通图，k=1，2
κ(G)=1， λ(G)=2
定理 对于任何无向图G，有 κ(G)≤λ(G)≤δ(G)
（1）多重集合 （2）无序积 （3）无向图
顶点、边（无向边） 例1 如图，V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v2,v3),
(v2,v3), (v2,v5), (v1,v5), (v4,v5)} （4）有向图
顶点、边（有向边） 例2 如右图，试写出它的V和E。
否则称G为非连通图。
如图G1是非连通图， G2是连通图。
G1
G2
21
连通分支：设无向图G=<V, E>，V关于顶点之间的 连通关系 的商集 V/ ={V1,V2,…,Vk}，Vi为等价 类，称导出子图G[Vi] (i=1,2,…,k) 为G的连通分 支, 其个数记作p(G)=k。
如： p(G1)=2， p(G2)=1 G是连通图 p(G)=1 n阶零图的连通分支数最多， p(Nn)=n
n
a(l ) ii
为D中长度为
l
的回路总数。
i1
36
推论 设Bl=A+A2+…+Al(l1), 则Bl中元素 nn
bi(jl)为D中长度小于或等于l 的通路数，
若u不可达v, 规定d<u,v>=∞.
性质： d<u,v>0, 且d<u,v>=0 u=v d<u,v>+d<v,w> d<u,w> 注意：没有对称性
30
（30）二部图
定义：
二部图：无向图G, V1V2=V, V1V2=, V1≠， V2≠, G中每条边的两个端点都一个属于V1, 另一 个属于V2，记为<V1, V2, E>。
28
练习1 如右图，分别求：
a
(1) a, d之间所有不同的通路；
(2) a, d之间的短程线；
b
(3) d(a, d)。
练习2 判断以下
有向图的连通性。
(1)
(2)
ed c
(3)
(4)
(5)
(6)
29
（29）有向图的短程线与距离
短程线： vi到vj长度最短的通路 (vi可达vj)。 距离d< vi, vj >： vi到vj 的短程线的长度。
22
（24）无向图的短程线与距离
短程线：u与v之间长度最短的通路。 （路） 距离d(u,v)：u与v之间短程线的长度。 （数）
规定，若u与v不连通，d(u,v)=∞。 性质：
d(u,v)0, 且d(u,v)=0 u=v d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)
23
（25）点割集 定义： 点割集 割点
有圈的长度2。
• 复杂通路和复杂回路： 中的边重复出现。
20
14.3 图的连通性
（23）无向图的连通性 设无向图G=<V, E>，u, vV， u与v连通：u与v之间存在通路. 记作uv. 规定uu。 连通关系： ={<u,v>| u,vV且uv}是等价关系。 连通图：平凡图, 任意两点都连通的图。
称V1和V2为互补顶点子集。 完全二部图：若G是简单图, 且V1中每个顶点均与 V2中每个顶点都相邻， 记为Kr,s, 其中r=|V1|, s=|V2|.
例如： K3,3 ， K2,3 注意: n 阶零图为二部图。
31
二部图的判别法： 定理 无向图G=<V, E>是二部图 G中无奇圈。 例16 下述各图都是二部图