<4D F736F F F696E74202D20CDBCC2DB2D31342ECDBCB5C4BBF9B1BEB8C5C4EE2E707074>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20CDBCC2DB2D31342ECDBCB5C4BBF9B1BEB8C5C4EE2E707074>"

朝赖禄
5 years ago
Views:

1 图论王智慧复旦大学计算机学院

2 图的基本概念图的概念通路与回路图的连通性图的矩阵表示图的运算 2

3 无序积, 多重集定义 : 设 A 和 B 为任意的两个集合, 称 { {a, b} a A, b B } 为 A 与 B 的无序积, 记做 A&B. 定义 : 元素可以重复出现的集合称为多重集, 其中某元素重复出现的次数称为该元素的重复度. 例如 : {a, a, b} 为一个多重集, 其中元素 a 的重复度为 2, 元素 b 的重复度为 1. 3

4 无向图与有向图的概念定义 : 一个无向图是一个有序的二元组 G = <V, E>, 其中 (1) V φ 称为顶点集, 其元素称为顶点或结点 ; (2) E 称为边集, E = { (v i, v j ) v i, v j V} 是无序积 V&V 的多重子集, 其中 (v i, v j ) 称为无向边 ( 或简称边 ). 定义 : 一个有向图是一个有序的二元组 D = <V, E>, 其中 : (1) V φ 称为顶点集, 其元素称为顶点或结点 ; (2) E 称为边集, E = { <v i, v j > v i, v j V} 是笛卡儿积 V V 的多重子集, 其中 <v i, v j > 称为有向边. 4 通常情况下, 无向图和有向图都可以用图形来直观表示, 即 : 用小圆圈 ( 或实心点 ) 表示顶点, 用顶点之间的连线表示无向边, 用有方向的连线表示有向边.

5 基本概念在图的定义中, 有时也用 G 来泛指图 ( 包括无向图和有向图 ), 用 V(G) 和 E(G) 分别表示图 G 的顶点集和边集 ; V(G) 和 E(G) 分别表示图 G 的顶点数和边数. 如果 V(G) = n, 则称 G 为 n 阶图 ; 若 V(G) 与 E(G) 均为有限数, 则称 G 为有限图. 在图 G 中, 如果边集 E(G) = φ, 则称 G 为零图 ; 此时, 若 G 为 n 阶图, 则称 G 为 n 阶零图, 记作 N n ; 特别地, 称 N 1 为平凡图. 5

6 基本概念在图的定义中, 我们规定顶点集 V 为非空集, 但在图的运算中可能产生顶点集为空集的运算结果, 为此规定顶点集为空集的图为空图, 并将空图记为. 在将图的集合定义转化成图形表示之后, 常用 e k 表示无向边 (v i, v j )( 或有向边 <v i, v j >), 称顶点或边用字母标定的图为标定图, 否则, 称为非标定图. 将有向图各有向边改成无向边后的无向图称为原来图的基图. 6

7 基本概念设 G = <V, E> 为无向图, e k = (v i, v j ) E, 则称 v i, v j 为 e k 的端点, e k 与 v i 或 e k 与 v j 是彼此相关联的 ; 若 v i v j, 则称 e k 与 v i 或 e k 与 v j 的关联次数为 1; 若 v i = v j, 则称 e k 与 v i 的关联次数为 2, 并称 e k 为环 ; v s V, 若 v s v i 且 v s v j, 则称 e k 与 v s 的关联次数为 0; 设 D = <V, E> 为有向图, e k = <v i, v j > E, 称 v i, v j 为 e k 的端点 ; 若 v i = v j, 则称 e k 为 D 中的环 ; 无论在无向图中还是有向图中, 无边关联的顶点称为孤立点. 7

8 基本概念设无向图 G = <V, E>, v i, v j V, e k, e s E. 若 e t E, 使得 e t = (v i, v j ), 则称 v i 与 v j 是相邻的. 若 e k 与 e s 至少有一个公共端点, 则称 e k 与 e s 是相邻的设有向图 D = <V, E>, v i, v j V, e k, e s E. 若 e t E, 使得 e t = <v i, v j >, 则称 v i 为 e t 的始点, v j 为 e t 的终点, 并称 v i 邻接到 v j, v j 邻接于 v i. 若 e k 的终点为 e s 的始点, 则称 e k 与 e s 相邻 8

9 基本概念设无向图 G = <V, E>, v V, 称 { u u V (u, v) E u v } 为 v 的邻域, 记做 N G (v); 称 N G (v) { v } 为 v 的闭邻域, 记做 ; 称 { e e E e 与 v 相关联 } 为 v 的关联集, 记做 I G (v) N () G v 设有向图 D = <V, E>, v V, 称 { u u V <v, u> E u v } 为 v 的后继元集, 记做 Γ + D (v); 称 { u u V <u, v> E u v } 为 v 的先驱元集, 记做 Γ - D (v); 称 Γ + (v) Γ - (v) 为 v 的邻域, 记做 N D (v); 称 N D (v) { v } 为 v 的闭邻域, 记做 N () D v 9

10 平行边, 多重图, 简单图定义 : 在无向图中, 若关联一对顶点的无向边多于 1 条, 则称这些边为平行边, 平行边的条数称为重数. 在有向图中, 若关联一对顶点的有向边多于 1 条, 并且这些边的起点与终点相同 ( 即边的方向相同 ), 则称这些边为平行边. 含平行边的图称为多重图 ; 既不含平行边, 也不含环的图称为简单图. 10

11 图的度数定义 : 设 G = <V, E> 为一无向图, v V, 称 v 作为边的端点次数之和为 v 的度数, 简称为度, 记做 d G (v), 在不发生混淆时, 简记为 d(v); 设 D = <V, E> 为有向图, v V, 称 v 作为边的始点次数之和为 v 的出度, 记做 d + D (v), 简记作 d + (v); 称 v 作为边的终点次数之和为 v 的入度, 记做 d - D (v), 简记作 d - (v); 称 d + (v)+d - (v) 为 v 的度数, 记做 d(v). 11

12 图的度数定义 : 设 G = <V, E> 为一无向图, 令 Δ(G)=max{d(v) v V(G)}, δ(g) = min{d(v) v V(G)}, 称 Δ(G), δ(g) 分别为 G 的最大度和最小度. 设 D = <V, E> 为有向图, 在有向图 D 中, 类似可定义最大度 Δ(G) 和最小度 δ(g). 另外, 令 Δ + (G)=max{d + (v) v V(G)}, δ + (G)=min{d + (v) v V(G)}, Δ - (G)=max{d - (v) v V(G)}, δ - (G)=min{d - (v) v V(G)}, 分别称为 D 的最大出度, 最小出度, 最大入度, 最小入度. 当不会引起混淆时, 以上记号可分别简记为 Δ, δ, Δ +, δ +, Δ -, δ -. 此外, 称度数为 1 的顶点为悬挂顶点, 与它关联的边称为悬挂边. 度数为偶数 ( 奇数 ) 的顶点称为偶度 ( 奇度 ) 顶点. 12

13 握手定理定理 : 设 G = <V, E> 为任意无向图, V = { v 1, v 2,, v n }, E = m, 则 Σ i=1..n d(v i ) = 2m 证明 : G 中每条边 ( 包括环 ) 均有两个端点, 在计算 G 中各顶点度数之和时, 每条边均提供 2 度, 所以, m 条边共提供 2m 度定理 : 设 D = <V, E> 为任意有向图, V = { v 1, v 2,, v n }, E = m, 则 Σ i=1..n d(v i ) = 2m, Σ i=1..n d + (v i ) = Σ i=1..n d - (v i ) = m 该定理的证明与上面的定理类似. 13

14 握手定理握手定理的推论 : 任何图 ( 无向的或有向的 ) 中, 奇度顶点的个数是偶数证明 : 设 G = <V, E> 为任意图, 令 V 1 = { v v V, d(v) 为奇数 }, V 2 = { v v V, d(v) 为偶数 } 则 V 1 V 2 = V, V 1 V 2 = φ 由握手定理可知 : 2m = Σ v V d(v) = Σ v V1 d(v) + Σ v V2 d(v) 由 2m 和 Σ v V2 d(v) 均为偶数可知 Σ v V1 d(v) 也为偶数因为 V 1 中各顶点的度数都为奇数, 所以 V 1 必为偶数 14

15 度数列设 G = <V, E> 为一个 n 阶无向图, V = { v 1, v 2,, v n }, 称 d(v 1 ), d(v 2 ),, d(v n ) 为 G 的度数列. 对于顶点标定的无向图, 它的度数列是唯一的设 D = <V, E> 为一个 n 阶有向图, V = { v 1,v 2,, v n }, 称 d(v 1 ), d(v 2 ),, d(v n ) 为 D 的度数列, 称 d + (v 1 ), d + (v 2 ),, d + (v n ) 与 d - (v 1 ), d - (v 2 ),, d - (v n ) 分别为 D 的出度列和入度列 15

16 可图化对于给定的非负整数列 d = (d 1, d 2,, d n ), 若存在以 V = { v 1, v 2,, v n } 为顶点集的 n 阶无向图 G, 使得 d(v i ) = d i, 则称 d 是可图化的特别地, 若所得图是简单图, 则称 d 是可简单图化的给定非负整数列 d = (d 1, d 2,, d n ), 如何判断其是否可图化的? 可以使用下列定理. 定理 : 设非负整数列 d = (d 1, d 2,, d n ), 则 d 是可图化的, 当且仅当 Σ i=1..n d i = 0 (mod 2). 16

17 可图化 17 定理 : 设非负整数列 d = (d 1, d 2,, d n ), 则 d 是可图化的, 当且仅当 Σ i=1..n d i = 0 (mod 2). 证明 : 由握手定理可知 : 必要条件是显然的下面证明其充分性由已知条件可知 : d 中有 2k(0 k n/2 ) 个奇数不妨设这些奇数为 : d 1, d 2,, d k, d k+1, d k+2,, d 2k 做出 n 阶无向图 G = <V, E>, V = { v 1, v 2,, v n } 的方法如下 : 首先, 在顶点 v r 与 v r+k 之间连边 (r = 1..k); 若 d i 为偶数, 令 d i = d i ; 若 d i 为奇数, 令 d i = d i -1, 得 d =(d 1,d 2,, d n ), 其中 d i 均为偶数. 再在 v i 处做出 d i /2 条环 (i = 1..n), 将所得各边集合在一起组成 E, 则 G 的度数列为 d.

18 可图化定理 : 设 G 为任意 n 阶无向简单图, 则 Δ(G) n-1 证明 : 因为 G 是简单图, 所以 G 中无平行边, 也无环. 这样, G 中任何顶点 v 至多与其余 n-1 个顶点相邻, 即 d(v) n-1 由 v 的任意性可知 : Δ(G) n-1 18

19 图的同构定义 : 设 G 1 =<V 1, E 1 >, G 2 =<V 2, E 2 > 为两个无向图 ( 两个有向图 ) 若存在双射函数 f: V 1 V 2, 对于 v i, v j V 1, (v i, v j ) E 1 (<v i, v j > E 1 ), 当且仅当 (f(v i ), f(v j )) E 2 (<f(v i ), f(v j )> E 2 ), 并且 (v i, v j ) (<v i, v j >) 与 (f(v i ), f(v j ))(<f(v i ), f(v j )>) 的重数相同, 则称 G 1 与 G 2 是同构的 (Isomorphic), 记作 : G 1 G 2. 19

20 图的同构图之间的同构关系可看成全体图集合上的二元关系, 该二元关系是自反对称和传递的, 因此, 它是等价关系在同构关系的每个等价类中取一个非标定图作为其代表, 凡与它同构的图, 在同构含义下都可看成一个图 20

21 图的同构说明 : 注意 : 不要将两个图同构的必要条件当成充分条件. 若 G 1 G 2, 则它们的阶数边数和度数列等都相同若不满足这些条件之一, 则两个图肯定不同构 ; 但是, 若满足这些条件, 两个图也不一定同构 21

22 完全图定义 : 设 G 为 n 阶无向简单图, 若 G 中每个顶点均与其余的 n-1 个顶点相邻, 则称 G 为 n 阶无向完全图 (Complete Graph), 简称 n 阶完全图, 记做 K n (n 1); 设 D 为 n 阶有向简单图, 若 D 中每个顶点都邻接到其余的 n-1 个顶点, 又邻接于其余的 n-1 个顶点, 则称 D 是 n 阶有向完全图 ; 设 D 为 n 阶有向简单图, 若 D 的基图为 n 阶无向完全图 K n, 则称 D 是 n 阶竞赛图 22

23 k- 正则图定义 : 设 G 为 n 阶无向简单图, 若 v V(G), 均有 d(v) = k, 则称 G 为 k- 正则图 n 阶零图是 0- 正则图, n 阶无向完全图是 (n-1)- 正则图, 彼得松图是 3- 正则图由握手定理可知 : n 阶 k- 正则图中, 边数 m = kn/2 所以, 当 k 为奇数时, n 必为偶数 23

24 子图定义 : 设 G = <V, E>, G = <V, E > 为两个图 ( 同为无向图或有向图 ), 若 V V 且 E E, 则称 G 是 G 的子图 (Subgraph), G 为 G 的母图, 记作 G G; 若 V V 或 E E, 则称 G 为 G 的真子图 ; 若 V = V, 则称 G 为 G 的生成子图 24

25 导出子图定义 : 设图 G = <V, E>, 如果 V 1 V, V 1, 称以 V 1 为顶点集, 以 G 中两个端点都在 V 1 中的边组成边集 E 1 的图为 G 的 V 1 导出的子图, 记作 G[V 1 ]; 设图 G = <V, E>, 如果 E 1 E, E 1, 称以 E 1 为边集, 以 E 1 中边关联的顶点为顶点集 V 1 的图为 G 的 E 1 导出的子图, 记作 G[E 1 ] 25

26 补图定义 : 设 G = <V, E> 为 n 阶简单无向图, 以 V 为顶点集, 以使 G 成为完全图 K n 的所有添加边组成的集合为边集的图, 称为 G 的补图 (Complement Graph), 记做 G 若图 G G, 则称 G 是自补图 26

27 图的变化定义 : 设 G = <V, E> 为无向图, (1) 设 e E, 用 G-e 表示从 G 中去掉边 e, 称为删除边 e 又设 E E, 用 G-E 表示从 G 中删除 E 中的所有边, 称为删除 E ; (2) 设 v V, 用 G-v 表示从 G 中去掉 v 及其所关联的一切边, 称为删除顶点 v; 设 V V, 用 G-V 表示从 G 删除 V 中所有顶点及其所关联的边, 称为删除 V ; (3) 设边 e = (u, v) E, 用 G\e 表示从 G 中删除 e, 并将端点 u, v 用一个新的顶点 w( 或用 u 或 v 充当 w) 来代替, 使 w 关联 e 以外 u, v 关联的所有边, 称为边 e 的收缩 ; (4) 设 u, v V(u, v 可能相邻, 也可能不相邻 ), 用 G (u, v)( 或 G+(u, v)) 表示在 u, v 之间加一条边 (u, v), 称为新加边 27 在收缩边和加新边过程中可能产生环和平行边

28 通路与回路定义 : 设 G 为无向标定图, G 中顶点与边的交替序列 Γ=v i0 e j1 v i1 e j2 e js v is 称为 v i0 到 v is 的通路 ; 其中, v ir-1,v ir 为 e jr 的端点, r = 1..s 28 v i0 和 v is 分别称为 Γ 的始点与终点 ; Γ 中边数称为它的长度 ; 若 v i0 = v is, 则称通路为回路 ; 若 Γ 的所有边都不相同, 则称 Γ 为简单通路 ; 此时若 v i0 = v is, 则称 Γ 为简单回路 ; 若 Γ 的所有顶点 ( 除端点外 ) 都不相同, 所有边也都不同, 则称 Γ 为初级通路或路径 ; 此时若 v i0 = v is, 则称 Γ 为初级回路或圈 ; 长度为奇数 ( 偶数 ) 的圈称为奇圈 ( 偶圈 ); 若 Γ 中有边重复出现, 则称 Γ 为复杂通路 ; 此时若 v i0 = v is, 则称 Γ 为复杂回路.

29 通路与回路注意 : 在上述定义中, 回路是通路的特殊情况, 即回路也是通路, 初级通路 ( 回路 ) 是简单通路 ( 回路 ), 但反之不真 ; 在有向图中, 通路回路的相关定义与上述无向图中类似, 只是要注意有向边方向的一致性 ; 为了写出非标定图中的通路 ( 或回路 ), 可以先将非标定图标成标定图, 再写出通路 ( 或回路 ). 29

30 通路与回路除了用上述顶点与边的交替序列来定义通路和回路, 还可用更简单的表示法来表示通路和回路 : 用边的序列表示通路 ( 回路 ), Γ 可表示成 Γ = e j1 e j2 e js 在简单图中也可用顶点序列表示通路 ( 回路 ), Γ 也可表示成 Γ = v i0 v i1 v is 30

31 通路与回路定理 : 在 n 阶图 G 中, 若从顶点 v i 到 v j (v i v j ) 存在通路, 则从 v i 到 v j 存在长度小于或等于 (n-1) 的通路证明 : 设 Γ = v 0 e 1 v 1 e 2 e t v t (v 0 =v i, v t =v j ) 为 G 中一条长度为 t 的通路. 当 t n-1 时, 则 Γ 满足要求 ; 当 t > n-1, 由于 Γ 上的顶点数多于 G 中的顶点数, 必存在 0 k<s t, 使得 v s = v k, 即在 Γ 上存在 v s 到 v k 的回路 C sk 在 Γ 上删除 C sk 中的所有边和除 v s 外的所有顶点, 可得 Γ = v 0 e 1 v 1 e 2 v s e s+1 e t v t 此时, Γ 仍为 v i 到 v j 的通路, 且长度 t 至少比 Γ 的长度少 1 若 Γ 的长度 t 仍然大于 n-1, 则重复上述过程由于 G 是有限图, 经过有限步后, 必得到从 v i 到 v j 长度小于或等于 n-1 的通路 31

32 通路与回路推论 : 在 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 到自身的简单回路, 则一定存在 v i 到自身长度小于或等于 n 的初级回路 32

33 通路与回路例 : 无向完全图 K n (n 3) 中有多少种非同构的圈? 解 : 由于长度相同的圈都是同构的 ( 因为可以构造相应的双射 ), 所以只有长度不同的圈才是非同构的而 K n (n 3) 中圈的长度只能有 3, 4,, n, 因此, K n 中最多只有 n-2 种非同构的圈在同构意义下, 给定长度的圈只有一个在标定图中, 圈表示成顶点和边的标记序列如果只要两个标记序列不同, 就认为这两个圈不同, 称这两个圈在定义意义下不同 33

34 通路与回路例 : 无向完全图 K 3 的顶点依次标定为 a, b 和 c 在定义意义下 K 3 中有多少个不同的圈? 解 : 在同构意义下, K 3 中只有一个长度为 3 的圈但在定义意义下, 不同起点 ( 终点 ) 的圈是不同的, 顶点间排列顺序不同的圈也是不同的因此, K 3 中有 6 个不同的长为 3 的圈 : abca, acba, bacb, bcab, cabc 和 cbac 如果只考虑起点 ( 终点 ) 的差异, 而不考虑顺时针逆时针的差异, 那么仅有 3 种不同的圈 34

35 无向图的连通性定义 : 设无向图 G = <V, E>, u, v V, 若 u 与 v 之间存在通路, 则称 u 和 v 是连通的, 记作 : u ~ v; v V, 规定 : v ~ v; 无向图中顶点之间的连通关系 ~ 可以做如下解释 : ~ = { (u, v) u,v V, u 与 v 之间有通路 } 显然, ~ 是自反对称和传递的, 所以, ~ 是 V 上的等价关系定义 : 若无向图 G 是平凡图或 G 中任何两顶点都是连通的, 则称 G 为连通图, 否则称 G 是非连通图或分离图例如 : 完全图 K n (n 1) 是连通图, 而零图 N n (n 2) 是分离图 35

36 连通分支定义 : 设无向图 G = <V, E>, V 关于顶点之间的连通关系 ~ 的商集 V/~ = { V 1, V 2,, V k }, V i 为等价类, 称导出子图 G[V i ] (i = 1..k) 为 G 的连通分支 ; 连通分支数 k, 常记为 p(g) 根据定义可知 : 若 G 为连通图, 则 p(g) = 1; 若 G 为非连通图, 则 p(g) 2; 在所有的 n 阶无向图中, n 阶零图是连通分支最多的, p(n n ) = n 36

37 点之间的距离定义 : 设 u, v 为无向图 G 中任意两个顶点, 若 u ~ v, 称 u 和 v 之间长度最短的通路为 u 和 v 之间的短程线 ; 短程线的长度称为 u 和 v 之间的距离, 记作 d(u, v). 当 u 和 v 不连通时, 规定 d(u, v) = 距离具有以下性质 : d(u, v) 0, 当 u = v 时, 等号成立 ; 对称性, d(u, v) = d(v, u); 满足三角不等式 : u,v,w V(G), 则 d(u, v) + d(v, w) d(u, w) u,v V(K n )(n 2), d(u, v) = 1; u,v V(N n )(n 2), d(u, v) =. 37

38 点割集与割点定义 : 设无向图 G = <V, E>, 若存在 V V, 且 V φ, 使得 : p(g V ) > p(g), 而对于任意的 V V, 均有 p(g V ) = p(g), 则称 V 是 G 的点割集 ; 若 V = { v }( 即 V 为单元集 ), 则称 v 为割点 38

39 边割集与割边定义 : 设无向图 G = <V, E>, 若存在 E E, E φ, 使得 p(g E ) > p(g), 而对于任意的 E E, 都有 : p(g E ) = p(g), 则称 E 是 G 的边割集, 或简称为割集 ; 若 E = { e }( 即 E 为单元集 ), 则称 e 为割边或桥 39

40 点连通度与边连通度定义 : 设 G 为无向连通图且不是完全图, 则称 κ(g) = min{ V V 为 G 的点割集 } 为 G 的点连通度, 简称连通度 κ(g) 简记为 κ ( 读 : kæpə) 规定 : 完全图 K n (n 1) 的点连通度为 n-1; 非连通图的点连通度为 0. 若 κ(g) k > 0, 则称 G 是 k- 连通图 40

41 点连通度与边连通度定义 : 设 G 是无向连通图, 称 λ(g) = min{ E E 是 G 的边割集 } 为 G 的边连通度, λ(g) 也可简记为 λ 规定 : 非连通图的边连通度为 0. 若 λ(g) r, 则称 G 是 r 边 - 连通图. 若 G 是 r 边 - 连通图, 则在 G 中任意删除 r-1 条边后所得的图仍是连通的完全图 K n 的边连通度为 n-1, 因此, K n 是 r 边 - 连通图 (0 r n-1) 设 G 1 和 G 2 都是 n 阶无向简单图, 若 κ(g 1 ) > κ(g 2 ), 则称 G 1 比 G 2 的点连通程度高若 λ(g 1 ) > λ(g 2 ), 则称 G 1 比 G 2 的边连通程度高 41 定理 : 对于任何无向图 G, 有 κ(g) λ(g) δ(g)

42 有向图的连通性定义 : 设 D = <V, E> 为有向图, v i,v j V, 若从 v i 到 v j 存在通路, 则称 v i 可达 v j, 记作 v i v j 规定 v i 总是可达自身的, 即 : v i v i. 若 v i v j 且 v j v i, 则称 v i 与 v j 是相互可达的, 记作 v i v j. 规定 v i v i 注意 : 与都是 V 上的二元关系, 且是 V 上的等价关系定义 : 设 D = <V, E> 为有向图, v i, v j V, 如果 v i v j, 则称 v i 到 v j 长度最短的通路为 v i 到 v j 的短程线 ; 短程线的长度为 v i 到 v j 的距离, 记作 d<v i, v j > 42 注意 : 与无向图中顶点之间的距离 d(v i, v j ) 相比, d<v i, v j > 除对称性外, 具有 d(v i, v j ) 所具有的其它性质

43 有向图的连通性定义 : 设 D = <V, E> 为有向图若 D 的基图是连通图, 则称 D 是弱连通图, 简称为连通图 ; 若 v i, v j V, v i v j 与 v j v i 至少其一成立, 则称 D 是单向连通图 ; 若均有 v i v j, 则称 D 是强连通图 43

44 强连通图与单向连通图的判别定理 : 设有向图 D = <V, E>, V = { v 1, v 2,, v n } D 是强连通图当且仅当 D 中存在经过每个顶点至少一次的回路证明 : 充分性显然成立下面证明必要性由 D 的强连通性可知 : v i v i+1, i = 1..n-1, 设 Γ i = v i v i+1. 又因为 v n v 1, 设 Γ n 为 V n 到 V 1 的通路, 则 Γ 1, Γ 2,, Γ n-1, Γ n 所围成的回路经过 D 中每个顶点至少一次定理 : 设 D 是 n 阶有向图, D 是单向连通图当且仅当 D 中存在经过每个顶点至少一次的通路 44

45 扩大路径法设 G = <V, E> 为 n 阶无向图, E φ, Γ s 为 G 中一条路径. 若此路径的始点或终点与通路外的顶点相邻, 就将它们扩到通路中, 继续该过程, 直到所通路的端点都不与通路外的顶点相邻为止设最后得到的路径为 Γ s+k ( 长度为 s 的路径扩大成了长度为 s+k 的路径 ), 称 Γ s+k 为极大路径, 称使用此种方法证明问题的方法为扩大路径法 45

46 扩大路径法 : 例子例 : 设 G 为 n(n 4) 阶无向简单图, δ(g) 3, 证明 G 中存在长度大于或等于 4 的圈证明 : 不妨设 G 是连通图, 否则, 因为 G 的各连通分支的最小度也都大于等于 3, 因而可对它的某个连通分支进行讨论设 u, v V(G). 由于 G 是连通图, 所以, 存在路径 u v. 用扩大路径法扩大这条路径 u v, 将最后得到的极大路径记为 Γ = v 0 v 1 v l, 因为 δ(g) 3, 所以有 l 3 若 v 0 与 v l 相邻, 则 Γ (v 0, v l ) 为长度大于等于 4 的圈 ; 否则, 由 d(v 0 ) δ(g) 3, 因而 v 0 除与 Γ 上的 v 1 相邻外, 还存在 Γ 上的顶点 v k (k 1) 和 v t (k < t l) 与 v 0 相邻, 则 v 0 v 1 v k v t v 0 为一个圈且长度大于或等于 4 46

47 二部图定义 : 设 G = <V, E> 为无向图, 若将 V 分成 V 1 和 V 2 (V 1 V 2 = V, V 1 V 2 = φ), 使得 (v i, v j ) E(G), 有 v i V 1, v j V 2, 则称 G 为二部图 ( 或称二分图, 偶图 ), 记为 <V 1, V 2, E>. 称 V 1 和 V 2 为互补顶点子集. 若 G 是简单二部图, V 1 中每个顶点均与 V 2 中所有顶点相邻, 则称 G 为完全二部图, 记为 K r,s, 其中 : r = V 1, s = V 2 47

48 二部图的判别定理 : 无向图 G = <V, E> 是二部图, 当且仅当 G 中无奇数长度的回路. 证明 : ( 必要性 ) 若 G 中无回路, 结论显然成立若 G 中有回路, 只需证明 G 中无奇圈设 C 为 G 中任意圈, 令 C = v i1 v i2 v is v i1, 易知 : s 2 不妨设 v i1 V 1, 则必有 v is V 2, 于是 s 必为偶数, 即 C 为偶圈, 由 C 的任意性可知结论成立 48

49 二部图的判别定理 : 无向图 G = <V, E> 是二部图, 当且仅当 G 中无奇数长度的回路. 49 证明 : ( 充分性 ) 设 G 为连通图, 否则, 可对每个连通分支进行讨论设 v 0 为 G 中任意一个顶点, 令 : V 1 = { v v V(G) d(v 0, v) 为偶数 } V 2 = { v v V(G) d(v 0, v) 为奇数 } 显然有 : V 1 V 2 = Ø, V 1 V 2 = V(G) 下面将证明 : V 1 (V 2 ) 中任意两顶点都不相邻假设 v i, v j V 1, e = (v i, v j ) E(G). 设 v 0 到 v i, v j 的短程线分别为 Γ i 和 Γ j, 则它们的长度 d(v 0, v i ), d(v 0, v j ) 都是偶数显然, Γ i Γ j e 中一定含奇圈, 这就与已知条件矛盾所以, V 1 (V 2 ) 中任意两顶点都不相邻, 即 G 为二部图

50 图的矩阵表示图可用集合来定义, 也可用图形来表达, 还可以用矩阵来表示用矩阵表示图便于用代数的方法研究图的性质, 也便于计算机处理图在用矩阵表示图时, 需将图的顶点或边标定顺序, 使其成为标定图本节将讨论无向 ( 有向 ) 图的关联矩阵, 有向图的邻接矩阵和可达矩阵 50

51 无向图的关联矩阵定义 : 设无向图 G = <V, E>, 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) 51

52 无向图关联矩阵的性质关联矩阵 M(G) 有以下性质 : Σ i=1..n m ij = 2 (j = 1..m), 即每列元素之和均为 2, 这正说明每条边关联两个顶点 ; Σ j=1..m m ij = d(v i ), 即 M(G) 第 i 行元素之和为 v i 的度数, i =1...n; Σ i=1..n d(v i ) = Σ i=1..n Σ j=1..m m ij = Σ j=1..m Σ i=1..n m ij = Σ i=1..m 2 = 2m, 即各顶点度数之和等于边数的 2 倍, 这个结果正是握手定理的内容 ; 第 j 列与第 k 列相同, 当且仅当边 e j 与 e k 是平行边 ; Σ j=1..m m ij = 0, 当且仅当 v i 是孤立点 52

53 有向图的关联矩阵定义 : 设有向图 D = <V, E> 中无环, V = { v 1, v 2,, v n }, E = { e 1, e 2,, e m }, 令 m ij 1 = 0 1 v 为 e i v 为 e i v 为 e i 的始点不关联的终点则称 (m ij ) n m 为 D 的关联矩阵, 记作 M(D) j j j 53

54 有向图关联矩阵的性质关联矩阵 M(D) 有以下性质 : Σ i=1..n m ij = 0(j = 1..m), 从而 Σ j=1..m Σ i=1..n m ij = 0, 也即 M(D) 中所有元素之和为 0; M(D) 中, -1 的个数等于 +1 的个数, 都等于边数 m, 这是有向图握手定理的内容 ; 第 i 行中, +1 的个数等于 v i 的出度, -1 的个数等于 v i 的入度 ; 平行边所对应的列相同 54

55 有向图的邻接矩阵定义 : 设有向图 D = <V, E>, V = { v 1, v 2,, v n }, E = { e 1, e 2,, e m }, 令 a ij 为 v i 邻接到 v j 边的条数, 称 (a ij ) n n 为 D 的邻接矩阵, 记作 A(D), 简记 A 55

56 有向图邻接矩阵的性质有向图的邻接矩阵有以下性质 Σ j=1..n a ij = d + (v i ) (i = 1..n), 即 A(D) 第 i 行元素之和为 v i 的出度 ; Σ i=1..n a ij =d - (v j ) (j = 1..n), 即 A(D) 第 j 列元素之和为 v j 的入度 ; Σ i=1..n Σ j=1..n a ij = Σ i=1..n d + (v i ) = m, Σ j=1..n Σ i=1..n a ij = Σ j=1..n d - (v j ) = m; 即反映了有向图握手定理同时, A(D) 中所有元素之和为 D 中长度为 1 的通路的个数, 而 Σ i=1..n a ii 为 D 中长度为 1 的回路 ( 环 ) 的个数 56

57 有向图邻接矩阵的性质如何利用 A(D), 计算出 D 中长度为 t 的通路数和回路数? ( 注 : 这里通路是定义意义下的概念, 不同起点的通路看成是不同的, 并且回路看成是通路的特殊情况 ) 为了解决提出的问题, 要计算 A(D) 的幂, 把 t 次幂记作 A t (D t ) 或简记作 A t 设 A t = (a ij (t) ) n n (t 2), 其中元素 a ij (t) = a ik (t-1) a kj (1), 则 a ij (t) 为顶点 v i 到 v j 长度为 t 的通路数, 当 i = j 时, a ii (t) 为 D 中从 v i 到 v i 长度为 t 的回路数 ( 这里的回路可是初级的, 简单的, 也可是复杂的 ). 57

58 有向图邻接矩阵的性质定理 : 设 A 为有向图 D 的邻接矩阵, D 的顶点集为 { v 1, v 2,, v n }, 则 A t (t 1) 中元素 a (t) ij 为 D 中 v i 到 v j 长度为 t 的通路数, 其中 a (t) ii 是长度为 t 的回路数 ; Σ i=1..n Σ j=1..n a (t) ij 是 D 中长度为 t 的通路总数, 其中 Σ i=1..n a (t) ii 是长度为 t 的回路总数推论 : 设 B t = A + A A t (t 1), 则 Σ i=1..n Σ j=1..n b (t) ij 为 D 中长度小于等于 t 的通路数, 其中 Σ i=1..n b (t) ii 为 D 中长度小于或等于 t 的回路数 58

59 有向图的可达矩阵定义 : 有向图 D = <V, E>, V = { v 1, v 2,, v n }, 令 : 若 v i 可达 v j, 则 p ij = 1, 否则, p ij = 0; 称 (p ij ) n n 为 D 的可达矩阵, 记作 P(D), 简记为 P; 注意 : 由于 v i V, v i v i, 所以, P(D) 主对角线上的元素全为 1 59

60 图的运算定义 : 设 G 1 = <V 1, E 1 >, G 2 = <V 2, E 2 > 为两个图, 若 V 1 V 2 = φ, 则称 G 1 与 G 2 是不交的 ; 若 E 1 E 2 = φ, 则称 G 1 与 G 2 是边不交或边不重的由定义可知, 不交的图必然是边不交的, 但反之不然 60

61 图的运算定义 : 设 G 1 = <V 1, E 1 >, G 2 = <V 2, E 2 > 为不含孤立点的两个图, 且它们同为无向图或有向图, 称以 E 1 E 2 为边集, 以 E 1 E 2 中边关联的顶点组成的集合为顶点集的图为 G 1 与 G 2 的并图, 记作 G 1 G 2 ; 称以 E 1 -E 2 为边集, 以 E 1 -E 2 中边关联的顶点组成的集合为顶点集的图为 G 1 与 G 2 的差图, 记作 G 1 -G 2 ; 称以 E 1 E 2 为边集, 以 E 1 E 2 中边关联的顶点组成的集合为顶点集的图为 G 1 与 G 2 的交图, 记作 G 1 G 2 ; 称以 E 1 E 2 为边集 ( 为集合之间的对称差运算 ), 以 E 1 E 2 中边关联的顶点组成的集合为顶点集的图为 G 1 与 G 2 的环和, 记作 G 1 G 2 61

62 图的运算在上述定义中, 应注意以下几点 : 若 G 1 = G 2, 则 G 1 G 2 = G 1 G 2 = G 1 而 G 1 -G 2 = G 2 -G 1 = G 1 G 2 = φ ( 这就是定义空图的原因 ) 当 G 1 与 G 2 边不重时, G 1 G 2 = φ G 1 -G 2 = G 1, G 2 -G 1 = G 2 G 1 G 2 = G 1 G 2 图之间环和的定义也可以用并交差来表达, 即 G 1 G 2 = (G 1 G 2 )-(G 1 G 2 ) 62

Microsoft PowerPoint - 10 几种特殊的图.ppt

Microsoft PowerPoint - 10 几种特殊的图.ppt 集合论与图论 10 目录二部图几种特殊的图欧拉图何英华 hyh@tju.edu.cn 哈密顿图平面图二部图设 G= 为一个无向图, 若能将 V 分成 V 1 和 V 2 (V 1 V 2 =V,V 1 V 2 = ), 使得 G 中的每条边的两个端点都是一个属于 V 1, 另一个属于 V 2, 则称 G 为二部图 ( 或称二分图, 偶图等 ), 称 V 1 和 V 2 为互补顶点子集,