1
图论
2
图论部分
?第 7章 图的基本概念
?第 8章 一些特殊的图
?第 9章 树
3
第 7章 图的基本概念
7.1 无向图及有向图
7.2 通路, 回路, 图的连通性
7.3 图的矩阵表示
4
7.1 无向图及有向图
?无向图与有向图
?顶点的度数
?握手定理
?简单图
?完全图
?子图
?补图
5
无向图与有向图
多重集合, 元素可以重复出现的集合
无序积, A?B={(x,y) | x?A?y?B}
定义 无向图 G=<V,E>,其中
(1) V??为顶点集, 元素称为 顶点
(2) E为 V?V的多重子集, 其元素
称为 无向边, 简称 边,
例如,G=<V,E>如图所示,
其中 V={v2,v2,…,v5},
E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}
6
无向图与有向图 (续 )
定义 有向图 D=<V,E>,其中
(1) V同无向图的顶点集,元素也称为 顶点
(2) E为 V?V的多重子集, 其元素
称为 有向边, 简称 边,
用无向边代替 D的所有有向边
所得到的无向图称作 D的 基图
右图是有向图,试写出它的 V和 E
注意：图的数学定义与图形表示,在
同构 (待叙 )的意义下是一一对应的
7
无向图与有向图 (续 )
通常用 G表示无向图,D表示有向图,也常用 G泛指
无向图和有向图,用 ek表示无向边或有向边,
V(G),E(G),V(D),E(D),G和 D的顶点集,边集,
n 阶图, n个顶点的图
有限图, V,E都是有穷集合的图
零图, E=?
平凡图, 1 阶零图
空图, V=?
8
顶点和边的关联与相邻
定义 设 ek=(vi,vj)是无向图 G=<V,E>的一条边,称 vi,vj为 ek的 端
点,ek与 vi ( vj)关联, 若 vi ? vj,则称 ek与 vi ( vj)的 关联次数为 1;
若 vi = vj,则称 ek为 环,此时称 ek与 vi 的 关联次数为 2; 若 vi不
是 ek端点,则称 ek与 vi 的 关联次数为 0,无边关联的顶点称作
孤立点,
定义 设无向图 G=<V,E>,vi,vj?V,ek,el?E,若 (vi,vj) ?E,则称
vi,vj相邻 ; 若 ek,el至少有一个公共端点,则称 ek,el相邻,
对有向图有类似定义, 设 ek=?vi,vj?是有向图的一条边,又称 vi是
ek的 始点,vj是 ek的 终点,vi邻接到 vj,vj邻接于 vi,
9
邻域和关联集
)(vN
)( vD??
}{)()( vvNvN DD ??
)( vD??
)()()( vvvN DDD ??? ?? ?
设无向图 G,v?V(G)
v的邻域 N(v)={u|u?V(G)?(u,v)?E(G)?u?v}
v的闭邻域 = N(v)∪ {v}
v的关联集 I(v)={e|e?E(G)?e与 v关联 }
设有向图 D,v?V(D)
v的后继元集 ={u|u?V(D)?<v,u>?E(G)?u?v}
v的先驱元集 ={u|u?V(D)?<u,v>?E(G)?u?v}
v的邻域
v的闭邻域
10
顶点的度数
设 G=<V,E>为无向图,v?V,
v的度数 (度 ) d(v),v作为边的端点次数之和
悬挂顶点, 度数为 1的顶点
悬挂边, 与悬挂顶点关联的边
G的最大度 ?(G)=max{d(v)| v?V}
G的最小度 ?(G)=min{d(v)| v?V}
例如 d(v5)=3,d(v2)=4,d(v1)=4,
?(G)=4,?(G)=1,
v4是悬挂顶点,e7是悬挂边,e1是环
11
顶点的度数 (续 )
设 D=<V,E>为有向图,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,
?+(D)=4,?+(D)=0,??(D)=3,
??(D)=1,?(D)=5,?(D)=3,
12
图论基本定理 —— 握手定理
定理 任意无向图和有向图的所有顶点度数之和都等
于边数的 2倍,并且有向图的所有顶点入度之和等
于出度之和等于边数,
证 G中每条边（包括环）均有两个端点，所以在计
算 G中各顶点度数之和时，每条边均提供 2度,m
条边共提供 2m度, 有向图的每条边提供一个入度
和一个出度,故所有顶点入度之和等于出度之和等
于边数,
13
握手定理 (续 )
???
???
???
21
)()()(2
VvVvVv
vdvdvdm
?
? 2
)(
Vv
vd ?
? 1
)(
Vv
vd
推论 在任何无向图和有向图中, 奇度顶点的个数必
为偶数,
证 设 G=<V,E>为任意图, 令
V1={v | v?V?d(v)为奇数 }
V2={v | v?V?d(v)为偶数 }
则 V1∪ V2=V,V1∩V2=?,由握手定理可知
由于 2m,均为偶数, 所以 也为偶数,但因为
V1中顶点度数都为奇数, 所以 |V1|必为偶数,
14
图的度数列
设无向图 G的顶点集 V={v1,v2,…,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+(v2),…,d+(vn)
D的入度列, d?(v1),d?(v2),…,d?(vn)
如右图度数列,5,3,3,3
出度列,4,0,2,1
入度列,1,3,1,2
15
握手定理的应用
例 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
16
握手定理的应用 (续 )
例 3 证明不存在具有奇数个面且每个面都具有奇数
条棱的多面体,
证 用反证法, 假设存在这样的多面体,
作无向图 G=<V,E>,其中 V={v | v为多面体的面 },
E={(u,v) | u,v?V ? u与 v有公共的棱 ? u?v},
根据假设,|V|为奇数且 ?v?V,d(v)为奇数, 这与握
手定理的推论矛盾,
17
多重图与简单图
定义 (1) 在无向图中,如果有 2条或 2条以上的边关
联同一对顶点,则称这些边为 平行边,平行边的
条数称为 重数,
(2)在有向图中,如果有 2条或 2条以上的边具有相同
的始点和终点,则称这些边为 有向平行边,简称
平行边,平行边的条数称为 重数,
(3) 含平行边的图称为 多重图,
(4) 既无平行边也无环的图称为 简单图,
注意,简单图是极其重要的概念
18
多重图与简单图 (续 )
例如
e5和 e6 是平行边
重数为 2
不是简单图
e2和 e3 是平行边,重数为 2
e6和 e7 不是平行边
不是简单图
19
图的同构
定义 设 G1=<V1,E1>,G2=<V2,E2>为两个无向图 (有
向图 ),若存在双射函数 f,V1?V2,使得对于任意的
vi,vj?V1,
(vi,vj)?E1（ <vi,vj>?E1）当且仅当
(f(vi),f(vj))?E2（ <f(vi),f(vj)>?E2）,
并且,(vi,vj)（ <vi,vj>）与 (f(vi),f(vj))（ <f(vi),f(vj)>）
的重数相同，则称 G1与 G2是 同构 的，记作 G1?G2,
20
图的同构 (续 )
几点说明,
图之间的同构关系具有自反性, 对称性和传递性,
能找到多条同构的必要条件,但它们都不是充分条件,
① 边数相同, 顶点数相同
② 度数列相同 (不计度数的顺序 )
③ 对应顶点的关联集及邻域的元素个数相同, 等等
若破坏必要条件, 则两图不同构
至今没有找到判断两个图同构的多项式时间算法
21
图的同构 (续 )
例 1 试画出 4阶 3条边的所有非同构的无向简单图
例 2 判断下述每一对图是否同构,
(1)
度数列不同
不同构
22
例 2 (续 )
(2)
不同构
入 (出 )度列不同
(3)
度数列相同
但不同构
为什么?
23
完全图与正则图
n阶无向完全图 Kn,每个顶点都与其余顶点相邻的 n
阶无向简单图,
简单性质, 边数 m=n(n-1)/2,?=?=n-1
n阶有向完全图, 每对顶点之间均有两条方向相反的
有向边的 n阶有向简单图,
简单性质, 边数 m=n(n-1),?=?=2(n-1),
?+=?+=?-=?-=n-1
n阶 k正则图, ?=?=k 的 n阶无向简单图
简单性质, 边数 m=nk/2
24
完全图与正则图 (续 )
(1) 为 5阶完全图 K5
(2) 为 3阶有向完全图
(3) 为彼得森图,它是 3 正则图
(1) (2) (3)
25
子图
定义 设 G=<V,E>,G ?=<V ?,E ?>是 2个图
(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 ?]
26
子图 (续 )
例 画出 K4的所有非同构的生成子图
27
补图
G
G
定义 设 G=<V,E>为 n阶无向简单图, 以 V为顶点集,
所有使 G成为完全图 Kn的添加边组成的集合为边集
的图, 称为 G的 补图, 记作,
若 G?,则称 G是 自补图,
例 对上一页 K4的所有非同构子图,指出互为补图的
每一对子图,并指出哪些是自补图,
图论
2
图论部分
?第 7章 图的基本概念
?第 8章 一些特殊的图
?第 9章 树
3
第 7章 图的基本概念
7.1 无向图及有向图
7.2 通路, 回路, 图的连通性
7.3 图的矩阵表示
4
7.1 无向图及有向图
?无向图与有向图
?顶点的度数
?握手定理
?简单图
?完全图
?子图
?补图
5
无向图与有向图
多重集合, 元素可以重复出现的集合
无序积, A?B={(x,y) | x?A?y?B}
定义 无向图 G=<V,E>,其中
(1) V??为顶点集, 元素称为 顶点
(2) E为 V?V的多重子集, 其元素
称为 无向边, 简称 边,
例如,G=<V,E>如图所示,
其中 V={v2,v2,…,v5},
E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}
6
无向图与有向图 (续 )
定义 有向图 D=<V,E>,其中
(1) V同无向图的顶点集,元素也称为 顶点
(2) E为 V?V的多重子集, 其元素
称为 有向边, 简称 边,
用无向边代替 D的所有有向边
所得到的无向图称作 D的 基图
右图是有向图,试写出它的 V和 E
注意：图的数学定义与图形表示,在
同构 (待叙 )的意义下是一一对应的
7
无向图与有向图 (续 )
通常用 G表示无向图,D表示有向图,也常用 G泛指
无向图和有向图,用 ek表示无向边或有向边,
V(G),E(G),V(D),E(D),G和 D的顶点集,边集,
n 阶图, n个顶点的图
有限图, V,E都是有穷集合的图
零图, E=?
平凡图, 1 阶零图
空图, V=?
8
顶点和边的关联与相邻
定义 设 ek=(vi,vj)是无向图 G=<V,E>的一条边,称 vi,vj为 ek的 端
点,ek与 vi ( vj)关联, 若 vi ? vj,则称 ek与 vi ( vj)的 关联次数为 1;
若 vi = vj,则称 ek为 环,此时称 ek与 vi 的 关联次数为 2; 若 vi不
是 ek端点,则称 ek与 vi 的 关联次数为 0,无边关联的顶点称作
孤立点,
定义 设无向图 G=<V,E>,vi,vj?V,ek,el?E,若 (vi,vj) ?E,则称
vi,vj相邻 ; 若 ek,el至少有一个公共端点,则称 ek,el相邻,
对有向图有类似定义, 设 ek=?vi,vj?是有向图的一条边,又称 vi是
ek的 始点,vj是 ek的 终点,vi邻接到 vj,vj邻接于 vi,
9
邻域和关联集
)(vN
)( vD??
}{)()( vvNvN DD ??
)( vD??
)()()( vvvN DDD ??? ?? ?
设无向图 G,v?V(G)
v的邻域 N(v)={u|u?V(G)?(u,v)?E(G)?u?v}
v的闭邻域 = N(v)∪ {v}
v的关联集 I(v)={e|e?E(G)?e与 v关联 }
设有向图 D,v?V(D)
v的后继元集 ={u|u?V(D)?<v,u>?E(G)?u?v}
v的先驱元集 ={u|u?V(D)?<u,v>?E(G)?u?v}
v的邻域
v的闭邻域
10
顶点的度数
设 G=<V,E>为无向图,v?V,
v的度数 (度 ) d(v),v作为边的端点次数之和
悬挂顶点, 度数为 1的顶点
悬挂边, 与悬挂顶点关联的边
G的最大度 ?(G)=max{d(v)| v?V}
G的最小度 ?(G)=min{d(v)| v?V}
例如 d(v5)=3,d(v2)=4,d(v1)=4,
?(G)=4,?(G)=1,
v4是悬挂顶点,e7是悬挂边,e1是环
11
顶点的度数 (续 )
设 D=<V,E>为有向图,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,
?+(D)=4,?+(D)=0,??(D)=3,
??(D)=1,?(D)=5,?(D)=3,
12
图论基本定理 —— 握手定理
定理 任意无向图和有向图的所有顶点度数之和都等
于边数的 2倍,并且有向图的所有顶点入度之和等
于出度之和等于边数,
证 G中每条边（包括环）均有两个端点，所以在计
算 G中各顶点度数之和时，每条边均提供 2度,m
条边共提供 2m度, 有向图的每条边提供一个入度
和一个出度,故所有顶点入度之和等于出度之和等
于边数,
13
握手定理 (续 )
???
???
???
21
)()()(2
VvVvVv
vdvdvdm
?
? 2
)(
Vv
vd ?
? 1
)(
Vv
vd
推论 在任何无向图和有向图中, 奇度顶点的个数必
为偶数,
证 设 G=<V,E>为任意图, 令
V1={v | v?V?d(v)为奇数 }
V2={v | v?V?d(v)为偶数 }
则 V1∪ V2=V,V1∩V2=?,由握手定理可知
由于 2m,均为偶数, 所以 也为偶数,但因为
V1中顶点度数都为奇数, 所以 |V1|必为偶数,
14
图的度数列
设无向图 G的顶点集 V={v1,v2,…,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+(v2),…,d+(vn)
D的入度列, d?(v1),d?(v2),…,d?(vn)
如右图度数列,5,3,3,3
出度列,4,0,2,1
入度列,1,3,1,2
15
握手定理的应用
例 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
16
握手定理的应用 (续 )
例 3 证明不存在具有奇数个面且每个面都具有奇数
条棱的多面体,
证 用反证法, 假设存在这样的多面体,
作无向图 G=<V,E>,其中 V={v | v为多面体的面 },
E={(u,v) | u,v?V ? u与 v有公共的棱 ? u?v},
根据假设,|V|为奇数且 ?v?V,d(v)为奇数, 这与握
手定理的推论矛盾,
17
多重图与简单图
定义 (1) 在无向图中,如果有 2条或 2条以上的边关
联同一对顶点,则称这些边为 平行边,平行边的
条数称为 重数,
(2)在有向图中,如果有 2条或 2条以上的边具有相同
的始点和终点,则称这些边为 有向平行边,简称
平行边,平行边的条数称为 重数,
(3) 含平行边的图称为 多重图,
(4) 既无平行边也无环的图称为 简单图,
注意,简单图是极其重要的概念
18
多重图与简单图 (续 )
例如
e5和 e6 是平行边
重数为 2
不是简单图
e2和 e3 是平行边,重数为 2
e6和 e7 不是平行边
不是简单图
19
图的同构
定义 设 G1=<V1,E1>,G2=<V2,E2>为两个无向图 (有
向图 ),若存在双射函数 f,V1?V2,使得对于任意的
vi,vj?V1,
(vi,vj)?E1（ <vi,vj>?E1）当且仅当
(f(vi),f(vj))?E2（ <f(vi),f(vj)>?E2）,
并且,(vi,vj)（ <vi,vj>）与 (f(vi),f(vj))（ <f(vi),f(vj)>）
的重数相同，则称 G1与 G2是 同构 的，记作 G1?G2,
20
图的同构 (续 )
几点说明,
图之间的同构关系具有自反性, 对称性和传递性,
能找到多条同构的必要条件,但它们都不是充分条件,
① 边数相同, 顶点数相同
② 度数列相同 (不计度数的顺序 )
③ 对应顶点的关联集及邻域的元素个数相同, 等等
若破坏必要条件, 则两图不同构
至今没有找到判断两个图同构的多项式时间算法
21
图的同构 (续 )
例 1 试画出 4阶 3条边的所有非同构的无向简单图
例 2 判断下述每一对图是否同构,
(1)
度数列不同
不同构
22
例 2 (续 )
(2)
不同构
入 (出 )度列不同
(3)
度数列相同
但不同构
为什么?
23
完全图与正则图
n阶无向完全图 Kn,每个顶点都与其余顶点相邻的 n
阶无向简单图,
简单性质, 边数 m=n(n-1)/2,?=?=n-1
n阶有向完全图, 每对顶点之间均有两条方向相反的
有向边的 n阶有向简单图,
简单性质, 边数 m=n(n-1),?=?=2(n-1),
?+=?+=?-=?-=n-1
n阶 k正则图, ?=?=k 的 n阶无向简单图
简单性质, 边数 m=nk/2
24
完全图与正则图 (续 )
(1) 为 5阶完全图 K5
(2) 为 3阶有向完全图
(3) 为彼得森图,它是 3 正则图
(1) (2) (3)
25
子图
定义 设 G=<V,E>,G ?=<V ?,E ?>是 2个图
(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 ?]
26
子图 (续 )
例 画出 K4的所有非同构的生成子图
27
补图
G
G
定义 设 G=<V,E>为 n阶无向简单图, 以 V为顶点集,
所有使 G成为完全图 Kn的添加边组成的集合为边集
的图, 称为 G的 补图, 记作,
若 G?,则称 G是 自补图,
例 对上一页 K4的所有非同构子图,指出互为补图的
每一对子图,并指出哪些是自补图,
