离散数学第七章图的基本概念知识点总结

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图: n 个顶点的图

有限图: V, E 都是有穷集合的图 零图: E =?

平凡图: 1 阶零图 空图: V =?

顶点和边的关联与相邻：定义 设e k =(v i ,v j )是无向图G =的一条边, 称v i ,v j 为e k 的端点, e k 与v i ( v j )关联. 若v i ≠ v j , 则称e k 与v i ( v j )的关联次数为1;若v i = v j , 则称e k 为环, 此时称e k 与v i 的关联次数为2; 若v i 不是e k 端点

,

2 / 1

3 则称e k 与v i 的关联次数为0. 无边关联的顶点称作孤立点. 定义 设无向图G =, v i ,v j ∈V , e k ,e l ∈E , 若(v i ,v j ) ∈E , 则称v i ,v j 相邻; 若e k ,e l 至少有一个公共端点, 则称e k ,e l 相邻.

对有向图有类似定义. 设e k =?v i ,v j ?是有向图的一条边,又称v i 是e k 的始点, v j 是e k 的终点, v i 邻接到v j , v j 邻接于v i .

邻域和关联集

顶点的度数

设G =为无向图, v ∈V ,

v 的度数(度) d (v ): v 作为边的端点次数之和 悬挂顶点: 度数为1的顶点

悬挂边: 与悬挂顶点关联的边

G 的最大度?(G )=max{d (v )| v ∈V }

G 的最小度δ(G )=min{d (v )| v ∈V }

例如 d (v 5)=3, d (v 2)=4, d (v 1)=4,?(G )=4, δ(G )=1,v 4是悬挂顶点, e 7是悬挂边, e 1是环

设D =为有向图, v ∈V ,

v 的出度d +(v ): v 作为边的始点次数之和

v 的入度d -(v ): v 作为边的终点次数之和

v 的度数(度) d (v ): v 作为边的端点次数之和 d (v )= d +(v )+ d -(v )

D 的最大出度?+(D ), 最小出度δ+(D )

最大入度?-(D ), 最小入度δ-(D )

最大度?(D ), 最小度δ(D )

例如 d +(a )=4, d -(a )=1, d (a )=5,

d +(b )=0, d -(b )=3, d (b

)=3,

3 / 13 ?+(D )=4, δ+(D )=0, ?-(D )=3,

δ-(D )=1, ?(D )=5, δ(D )=3.

握手定理

定理 任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数.

证 G 中每条边（包括环）均有两个端点，所以在计算G 中各顶点度数之和时，每条边均提供2度，m 条边共提供2m 度. 有向图的每条边提供一个入度和一个出度, 故所有顶点入度之和等于出度之和等于边数.

图的度数列

设无向图G 的顶点集V ={v 1, v 2, …, v n }

G 的度数列: d (v 1), d (v 2), …, d (v n )

如右图度数列:4,4,2,1,3

设有向图D 的顶点集V ={v 1, v 2, …, v n }

D 的度数列: d (v 1), d (v 2), …, d (v n )

D 的出度列: d +(v 1), d +(v 2), …, d +(v n )

D 的入度列: d -(v 1), d -(v 2), …, d -(v n )

如右图度数列:5,3,3,3

出度列:4,0,2,1

入度列

:1,3,1,2

例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗?

解不可能. 它们都有奇数个奇数.

例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G 至少有多少个顶点?

解设G有n个顶点. 由握手定理,

4?3+2?(n-4)≥2?10

解得n≥8

例3 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.

证用反证法. 假设存在这样的多面体,

作无向图G=, 其中V={v | v为多面体的面},

E={(u,v) | u,v∈V∧u与v有公共的棱∧u≠v}.

根据假设, |V|为奇数且?v∈V, d(v)为奇数. 这与握手定理的推论矛盾. 多重图与简单图

定义 (1) 在无向图中,如果有2条或2条以上的边关联同一对顶点, 则称这些边为平行边, 平行边的条数称为重数.

(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点, 则称这些边为有向平行边, 简称平行边, 平行边的条数称为重数.

(3) 含平行边的图称为多重图.

(4) 既无平行边也无环的图称为简单图.

注意:简单图是极其重要的概念

图的同构

定义设G1=, G2=为两个无向图(有

4 / 13

5 / 13 向图), 若存在双射函数 f : V 1→V 2, 使得对于任意的

v i ,v j ∈V 1,

(v i ,v j )∈E 1（∈E 1）当且仅当

(f (v i ),f (v j ))∈E 2（∈E 2）， 并且, (v i ,v j )（）与 (f (v i ),f (v j ))（） 的重数相同，则称G 1与G 2是同构的，记作G 1?G 2.

几点说明：

图之间的同构关系具有自反性、对称性和传递性.

能找到多条同构的必要条件, 但它们都不是充分条件:

① 边数相同，顶点数相同

② 度数列相同(不计度数的顺序)

③ 对应顶点的关联集及邻域的元素个数相同，等等

若破坏必要条件，则两图不同构

至今没有找到判断两个图同构的多项式时间算法

完全图：n 阶无向完全图K n : 每个顶点都与其余顶点相邻的n 阶无向简单图.

简单性质: 边数m =n (n -1)/2, ?=δ=n -1

n 阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n 阶有向简单图.

简单性质: 边数m =n (n -1), ?=δ=2(n -1),

?+=δ+=?-=δ-=n

-1

子图：定义设G=, G '=是两个图

(1) 若V '?V且E '?E,则称G '为G的子图, G为G '的

母图, 记作G '?G

(2) 若G '?G 且V '=V，则称G '为G的生成子图

(3) 若V '?V 或E '?E，称G '为G的真子图

(4) 设V '?V 且V '≠?, 以V '为顶点集, 以两端点都在

V '中的所有边为边集的G的子图称作V '的导

出子图，记作G[V ']

(5) 设E '?E且E '≠?, 以E '为边集, 以E '中边关联的

所有顶点为顶点集的G的子图称作E '的导出子

图, 记作G[E ']

补图：定义设G=为n阶无向简单图，以V为顶点集,所有使G成为完全图K n的添加边组成的集合为边集的图，称为G的补图，记作 .

若G? , 则称G是自补图.

例对上一页K4的所有非同构子图, 指出互为补图的每一对子图, 并指出哪些是自补图.

7.2 通路、回路、图的连通性

简单通(回)路, 初级通(回)路, 复杂通(回)路

定义给定图G=（无向或有向的），G中顶点与边的交替序列Γ=v0e1v1e2…e l v l，

(1) 若?i(1≤i≤l), v i-1, v i是e i的端点(对于有向图, 要求v i-1是始点, v i是终点), 则称Γ为通路, v0是通路的起点, v l是通路的终点, l为通路的长度. 又若v

=v l，则称Γ为回路.

(2) 若通路(回路)中所有顶点(对于回路, 除v0=v l)各异，则称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈.

(3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).

说明:

表示方法

① 用顶点和边的交替序列(定义), 如Γ=v0e1v1e2…e l v l

6 / 13

② 用边的序列, 如Γ=e1e2…e l

③ 简单图中, 用顶点的序列, 如Γ=v0v1…v l

④ 非简单图中,可用混合表示法,如Γ=v0v1e2v2e5v3v4v5

环是长度为1的圈, 两条平行边构成长度为2的圈.

在无向简单图中, 所有圈的长度≥3; 在有向简单图中, 所有圈的长度≥2.

在两种意义下计算的圈个数

① 定义意义下

在无向图中, 一个长度为l(l≥3)的圈看作2l个不同的圈. 如v0v1v2v0 ,

v 1v

2

v

v

1

, v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l≥3)的圈看作l个不同的圈.

② 同构意义下

所有长度相同的圈都是同构的, 因而是1个圈.

定理在n阶图G中，若从顶点v i到v j（v i≠v j）存在通

路，则从v i到v j存在长度小于等于n-1的通路.

推论在n阶图G中，若从顶点v i到v j（v i≠v j）存在通

路，则从v i到v j存在长度小于等于n-1的初级通路.

定理在一个n阶图G中，若存在v i到自身的回路，则

一定存在v i到自身长度小于等于n的回路.

推论在一个n阶图G中，若存在v i到自身的简单回

路，则一定存在长度小于等于n的初级回路.

无向图的连通性

设无向图G=,

u与v连通: 若u与v之间有通路. 规定u与自身总连通.

连通关系R={| u,v∈V且u~v}是V上的等价关系

连通图:任意两点都连通的图. 平凡图是连通图.

连通分支: V关于连通关系R的等价类的导出子图

设V/R={V1,V2,…,V k}, G[V1], G[V2], …,G[V k]是G的连通分支, 其个数记作p(G)=k.

G是连通图?p(G)=1

短程线与距离

u与v之间的短程线: u与v之间长度最短的通路

(u与v连通)

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)

点割集与割点

记G-v: 从G中删除v及关联的边

G-V ': 从G中删除V '中所有的顶点及关联的边

7 / 13

8 / 13 G -e : 从G 中删除e

G -E ': 从G 中删除E '中所有边

定义 设无向图G =, V '?V, 若p (G -V ')>p (G )且?V ''?V ', p (G -V '')=p (G ), 则称V '为G 的点割集. 若{v }为点割集, 则称v 为割点.

边割集与割边(桥)

定义 设无向图G =, E '?E, 若p (G -E ')>p (G )且?E ''?E ',

p (G -E '')=p (G ), 则称E '为G 的边割集. 若{e }为边割集, 则称e

为割边或桥.

在上一页的图中，{e 1,e 2}，{e 1,e 3,e 5,e 6}，{e 8}等是边割集，

e 8是桥，{e 7,e 9,e 5,e 6}是边割集吗？

几点说明：

K n 无点割集

n 阶零图既无点割集，也无边割集.

若G 连通，E '为边割集，则p (G -E ')=2

若G 连通，V '为点割集，则p (G -V ')≥2

有向图的连通性

设有向图D =

u 可达v : u 到v 有通路. 规定u 到自身总是可达的.

可达具有自反性和传递性

D 弱连通(连通): 基图为无向连通图

D 单向连通: ?u ,v ∈V ，u 可达v 或v 可达u

D 强连通: ?u ,v ∈V ，u 与v 相互可达

强连通?单向连通?弱连通

定理(强连通判别法) D 强连通当且仅当D 中存在经过每个顶点至少一次的回路 定理(单向连通判别法) D 单向连通当且仅当D 中存在经过每个顶点至少一次的通路

有向图的短程线与距离

u 到v 的短程线: u 到v 长度最短的通路 (u 可达v )

u 与v 之间的距离d: u 到v 的短程线的长度

9 / 13 若u 不可达v , 规定d=∞.

性质：

d≥0, 且d=0 ? u=v d+d ≥d

注意: 没有对称性

7.3 图的矩阵表示

无向图的关联矩阵

定义 设无向图G =, V ={v 1, v 2, …, v n }, E ={e 1, e 2, …, e m }, 令m ij 为v i 与e j 的关联次数，称(m ij )n ?m 为G 的关联矩阵，记为M (G ). 性质

(1) 每一列恰好有两个1或一个2

有向图的关联矩阵

定义 设无环有向图D =, V ={v 1, v 2, …, v n }, E ={e 1, e 2, …, e m }, 令

性质

(1) 每一列恰好有一个1和一个-1

(2) 第i 行1 的个数等于d +(v i ), -1 的个数等于d -(v i )

(3) 1的总个数等于-1的总个数, 且都等于m

(4) 平行边对应的列相同

有向图的邻接矩阵

有向图的可达矩阵

10 / 13

7.4 最短路径及关键路径

带权图G=, 其中w:E→R.

?e∈E, w(e)称作e的权. e=(v i,v j), 记w(e)=w ij . 若v i,v j不相邻, 记w ij =∞.

设L是G中的一条路径, L的所有边的权之和称作L的

权, 记作w(L).

u和v之间的最短路径: u和v之间权最小的通路.

标号法(E.W.Dijkstra, 1959)

11 / 13

PERT图与关键路径

PERT图(计划评审技术图)

设有向图G=, v∈V

v的后继元集Γ+(v)={x|x∈V∧∈E}

v的先驱元集Γ-(v)={x|x∈V∧∈E}

PERT图:满足下述条件的n阶有向带权图D=,

(1) D是简单图,

(2) D中无回路,

(3) 有一个入度为0的顶点, 称作始点; 有一个出度为0

的顶点, 称作终点.

通常边的权表示时间, 始点记作v1, 终点记作v n

关键路径

关键路径: PETR图中从始点到终点的最长路径

v

i

的最早完成时间TE(v i): 从始点v1沿最长路径到v i

所需的时间

TE(v

1

)=0

TE(v

i

)=max{TE(v j)+w ji|v j∈Γ-(v i)}, i=2,3,?,n

v

i

的最晚完成时间TL(v i): 在保证终点v n的最早完成

时间不增加的条件下, 从始点v1最迟到达v i的时间

TL(v

n

)=TE(v n)

TL(v

i

)=min{TL(v j)-w ij|v j∈Γ+(v i)}, i=n-1,n-2,?,1

v

i

的缓冲时间TS(v i)=TL(v i)-TE(v i), i=1,2,?,n

v i 在关键路径上?TS(v i)=0

12 / 13

最晚完成时间

TL(v

)=12

8

TL(v

)=min{12-6}=6

7

TL(v

)=min{12-1}=11

6

TL(v

)=min{11-1}=10

5

TL(v

)=min{10-4}=6

4

TL(v

)=min{6-2,11-4,6-4}=2

3

TL(v

)=min{2-0,10-3,6-4}=2

2

TL(v

)=min{2-1,2-2,6-3}=0

1

缓冲时间

TS(v

)=0-0=0

1

TS(v

)=2-1=1

2

TS(v

)=2-2=0

3

TS(v

)=6-4=2

4

TS(v

=10-8=2

5

TS(v

)=11-9=2

6

TS(v

)=6-6=0

7

TS(v

)=12-12=0

8

关键路径: v1v3v7v8

13 / 13