离散数学-第5章-3、4_图文

离散数学
Discrete Mathematics
汪荣贵 教授
合肥工业大学软件学院专用课件
2011.06
1

Chapter 5
graph theory

CHAPTER 5 Graphs
5.1 Introduction to Graphs 图的概述 5.2 Graph Terminology 图的术语 5.3 Representing Graphs and Graph Isomorphism图 的表示和图的同构 5.4 Connectivity 连通性 5.5 Euler and Hamilton Paths 欧拉通路和哈密顿通路 5.6 Planar Graphs and Graph Coloring 平面图与着色 5.7 Trees 树
3

5.3 Representing Graphs and Graph Isomorphism
Representing Graphs 图的表示
Methods for representing graphs: ? Adjacency lists 邻接表 -- lists that specify all the vertices that are adjacent to each vertex该表规定与图的每个顶点邻接的顶点 ? Adjacency matrice 邻接矩阵 ? Incidence matrices 关联矩阵
4 2019/9/14

Adjacency lists邻接表
例: 用邻接表描述所给的简单图
5 2019/9/14

Adjacency Matrices 邻接矩阵
若图里面有许多边,则把图表示成边表或邻接表, 就不便于执行图的算法。
为了简化计算,可用矩阵表示图。在这里将给出 两种类型的常用的表示图的矩阵:
一种类型是基于顶点的邻接关系, 一种类型是基于顶点与边的关联关系。
6 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
定义:假设 G = (V, E)是简单图 ,其中 |V|=n . 假 设 把 G 的 顶 点 任 意 地 排 列
成 v1, v2 ,?, vn 。对这个顶点表来说,G的邻
接矩阵A是一个n×n的0-1矩阵,它满足这 样的性质
aij = 1 if {vi, vj} is an edge of G, aij = 0 otherwise.
7 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

Note: Adjacency matrices of
undirected graphs are always symmetric.无向图的邻接矩阵总 是对称的

〖Example 1〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ? a

d

b

Solution:

?0 1 1 1?

AG

?

??1 ?1

0 0

0 0

1?? 1?

c

??1 1 1 0??

8 2019/9/14

注意: 1) 图的邻接矩阵依赖于所选择的顶点的顺序。因 此带n个顶点的图有n!个不同的邻接矩阵,因为n个 顶点有n!个不同的顺序。 2) 当图里的边相对少时,邻接矩阵是稀疏矩阵, 即只有很少的非0项的矩阵。可以用特殊的方法来表 示和计算这样的矩阵。
9 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

〖Example 2〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?

a

d

b

c

Solution:

Note: For undirected
multigraph or pseudograph ,
adjacency matrices are symmetric.无向多重图与伪 图都具有对称的邻接矩阵

?0 1 1 2?

AG

?

??1 ?1

1 0

0 0

1?? 3?

??2 1 3 0??

10 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
The adjacency matrix of a directed graph有向图的邻接矩阵
Let G = (V, E) be a directed graph with |V| = n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, …, vn. 假设G=(V,E)是含n个顶点的有向图。若 v1,v2,...,vn 是有向图 任意的顶点序列。
The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the n?n zero-one matrix with 1 as its (i, j)th entry when there is an edge from vi to vj, and 0 otherwise.若有向图G=(V,E)从 vi到v j 有边,则它的矩阵在(i,j)
位置上有1,否则为0
In other words, for an adjacency matrix A = [aij], aij = 1 if (vi, vj) is an edge of G, aij = 0 otherwise.
11 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

〖Example 3〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ? a
b d
c

Solution:
12 2019/9/14

?0 0 1 0?

AG

?

??1 ?0

0 0

0 0

0?? 0?

??1 1 1 0??

5.3 Representing Graphs and Graph Isomorphism
Question: 1. What is the sum of the entries in a row of the adjacency
matrix for an undirected graph? 对无向图来说,邻接矩阵每一行各个位置上数字之和代表什
么?

a

?0 1 1 2?

d

b

AG

?

??1 ?1

1 0

0 0

1?? 3?

c

??2 1 3 0??

13 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

Question:

1. What is the sum of the entries in a row of the adjacency
matrix for an undirected graph?对无向图来说,邻接矩阵每一
行各个位置上数字之和代表什么?

The number of edges incident to the vertex i, which is the
same as degree of i minus the number of loops at i.
与顶点i关联的边数等于顶点i的度减去在顶点i上的环数

For a directed graph? a b
d
c

?0 0 1 0?

AG

?

??1 ?0

0 0

0 0

0?? 0?

??1 1 1 0??

14 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
Question: 1. What is the sum of the entries in a row of the adjacency
matrix for an undirected graph? The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. For a directed graph?对于有向图而言,邻接矩阵每一行各个位置上
数字之和代表什么?代表该顶点的出度 deg+(vi)
2. What is the sum of the entries in a column of the adjacency matrix for an undirected graph? The number of edges incident to the vertex i, which is the same as degree of i minus the number of loops at i. For a directed graph?对于有向图而言,邻接矩阵每一列各个位置上 数字之和代表什么?代表该顶点的入度deg-(vi)
15 2019/9/14

? 置换矩阵:相当于将单位矩阵中相应的行与行, 或者列与列互换的矩阵。

100 P= 0 0 1
010
a11 a12 a13 PA = a31 a32 a33
a21 a22 a23

A=

a11 a12 a13 a21 a22 a23 a31 a32 a33

a11 a13 a12 (PA)P = a31 a33 a32
a21 a23 a22

P就是一个置换矩阵

? 邻接矩阵中图的性质:

v1

v3

v2

v4

无向图的邻接 矩阵是对称的!
0 1 10 A= 1 0 1 1
1 1 00 0 1 00

(1)A=(αij)n×n中,第i行或第i列中非0元素 的个数等于顶点vi的度。(无向图)

v1

v3

0 1 10

A= 0 0 0 1

0 1 01

v2

v4

1 0 10

竖入横出

(2) A=(αij)n×n中,第i列中非0元素的个数等于顶点 vi的入度,第i行中非0元素的个数等于顶点vi的 出度。(有向图)

(3) B=A2。

B=A2=

a11 a12 … a1n

a11 a12 … a1n

× a21 a22 … a2n

a21 a22 … a2n

……

……

an1 an2 … ann

an1 an2 … ann

=(bij)n×n

bij表示vi两步到达vj的路径数目

(4) 有向图中:C=AAT。

C= (cij)=

a11 a12 … a1n

a11 a21 … an1

× a21 a22 … a2n

a12 a22 … an2

……

……

an1 an2 … ann

a1n a2n … ann

cij=∑αik αjk

cij表示以vi,vj为始点的终点数目。 vi

vj

vk

(5) 有向图中:D=ATA。

D= (cij)=

a11 a21 … an1

a11 a12 … a1n

× a12 a22 … an2

a21 a22 … a2n

……

……

a1n a2n … ann

an1 an2 … ann

dij=∑αik αjk

vk

dij表示以vi,vj为终点的始点数目。

vi

vj

5.3 Representing Graphs and Graph Isomorphism
Incidence matrices 关联矩阵
设 G = (V, E) 是无向图.设.v1, v2 ,?, vn 是顶点而e1,e2 ,?,em 是边。则相对于V和E的这个顺序的关联矩阵是n×m矩阵
M ? [mij ]n?m

?1 mij ? ??0

whenedge e j is incident with vi otherwise

22 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

〖Example 4〗 What is the incidence matrix M for the

following graph G based on the order of vertices a, b, c, d

and edges 1, 2, 3, 4, 5, 6?

a1

2

b

Note:

d 35

4

c

Incidence matrices of undirected graphs contain two 1s per column for edges connecting two vertices and

Solution:

6

one 1 per column for loops.

a ?1 1 0 0 1 0? M ? b ??1 0 1 0 0 0??
c ?0 0 0 1 1 1? d ??0 1 1 1 0 0??

在无向图中的关联矩阵中,每列 中有两个1的表明这条边与 这两个顶点相连接,每列有 一个1的表明存在环

23 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
Isomorphism Of Graphs 图的同构

定义:设G1= (V1, E1) 和G2= (V2, E2)是简单图,若存在一对 一的和映上的从 V1 到V2 的函数f,且f具有这样的性质,
对V1里所有的a 和 b来说,a和b在 G1里邻接,当且仅当
f(a)和 f(b)在 G2里邻接,就说G1和G2是同构的。这样的
函数 f 称为同构.
换句话说,当两个简单图同构时,两个图的顶点之间 具有保持邻接关系的一一对应。

For example,

a

b

a' (b)

24 2019/9/14

d‘(d)

d

c

c' (a)

b' (c)

v1

v3

v2

v4

图G1

A1=

12 3 4
0 1 11 1 0 11 1 1 01 1 1 10

v1<->va v2<->vb v3<->vc v4<->vd

va

vb

vc

vd

图G2

A2=

ab c d
0 1 11 1 0 11 1 1 01 1 1 10

判别定理:图G1 ,G2同构的充要条件是:存在置换 矩阵P,使得:A1=PA2P。 其中A1,A2分别是G1 ,G2的邻接矩阵。
如何判断两图同构是图论中一个困难问题。

5.3 Representing Graphs and Graph Isomorphism
Question: 怎么判断两个简单图是否同构?
在两个带n个顶点的简单图顶点集之间有n!种可能的 一一对应,通过检验每一种对应来看它是否保持邻接关系 和不邻接关系是不可行的。
然而,可以通过说明两个简单图不具有同构的图所必 须具有的性质来说明 它们不同构。把这样的性质称为对 简单图的同构来说的不变量
invariants(不变量)
-- things that G1 and G2 must have in common to be isomorphic.
27 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
Important invariants in isomorphic graphs:同构图中的重要 不变量 ? 相同的顶点数 ? 有相同的边数 ? 有相同的顶点度 ? if one is bipartite, the other must be ? if one is complete, the other must be ? if one is a wheel, the other must be etc.
28 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

〖Example 5〗 Are the following two graphs isomorphic?

a

a

b

e

c

d

e

b

c

d

Solution: They are isomorphic, because they can be arranged to look identical. You can see this if in the right graph you move vertex b to the left of the edge {a, c}. Then the isomorphism f from the left to the right graph is: f(a) = e, f(b) = a, f(c) = b, f(d) = c, f(e) = d.
29 2019/9/14

5.3 Representing Graphs and Graph Isomorphism

〖Example 6〗 Show that the following two graphs are

isomorphic.

v1

v2

u1

u2

u5

v5

v4

v3

u4

u3

Proof: ? Check invariants ? Try to find an isomorphism f ? Show that f preserves adjacency relation

30 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
〖Example 7〗 Determine whether the given pair of graphs is isomorphic?
(1)
(2) (3)
31 2019/9/14

5.3 Representing Graphs and Graph Isomorphism
Homework: P. 467 8, 15, 17, 34-37
32 2019/9/14

CHAPTER 5 Graphs
5.1 Introduction to Graphs 图的概述 5.2 Graph Terminology 图的术语 5.3 Representing Graphs and Graph Isomorphism图 的表示和图的同构 5.4 Connectivity 连通性 5.5 Euler and Hamilton Paths 欧拉通路和哈密顿通路 5.6 Planar Graphs and Graph Coloring 平面图与着色 5.7 Trees 树
33

道路和回路
? 图G=(V,E)的一个顶点与边相交替的序列μ=v0e1v1…vk-1ekvk,且边ei的端
点为vi-1和vi (i=1,2,…,k),则称μ为一条道路(路径path),又称为v0-vk道 路。

v1

e2

v3

v5

e8

e1

e3

e5 e6

e7 e9

e10

v2

e4

v4

v6

e11

μ={v1 e2 v3 e5 v4}是一条道路

v7 e12
v8

若图G中的μ所有边均不相同——简单道路; 若道路μ中v0=vk(即首尾相同)——回路; 若回路μ中没有重复边——简单回路。

v1

e2

v3

v5

e8

v7

e1 v2

e3

e5 e6

e7 e9 e10

e12

e4

v4

v6

e11

v8

C= v5 e8 v7 e12 v8 e10 v6 e7 v5是一回路

顶点v1~v7代表七座城市,有方向的边vivj表示从 vi城到vj城的单行车道,问从v1城到v7城有无道路相 通? 如下图所示:
v1 v5

v2 v4
v7

v3

v6

通过观察上图容易得出解答。 如果我们进一步问:若v1城到v7有道
路相通,共有几条不同的道路?

考察邻接矩阵:

v1

v5

v2

v4 v3

v7

1234567

v6

1

2

3

A= 4

5

6

7

0100100 0000000 0100011 1010101 1001010 0010000 0000010

A2 =

A·A=

0100100 0000000 0100011 1010101 1001010 0010000 0000010

0100100 0000000 0100011 × 1010101 1001010 0010000 0000010

0×0+1×0+0×0+0×1+1×1+0×0+0×0=1

1001010

0000000

0010010



1201131 1120201

= (ai(j2) )

0100011

0010000

其中: 一般有: 其中:

A3 = A2·A=

1120201 0000000 0110011 2141221 2302152 0010010 0100011

= ? = ? a(3) ij

7

a (2) ik

a

kj

7

aik

a

(2) kj

k ?1

k ?1

Ak = (ai(jk) )7?7

7

a = ? (k ) ij

a a (k ?1)

ih

hj

h?1

= (ai(j3) )

现在来看看ai(jk的) 值有什么实际意义。以ai(j2为) 例:

? a = (2) ij

7
aik akj

= ai1a1 j

+ ai2 a2 j +…

+ ai7a7 j

k ?1

ail ? alj ? 0 当且仅当 ail ? alj ? 1

表示从 vi 出发两步到达 v j的路径数目 同理

a(k) ij

表示从

vi

出发k步到达v

j

的路径数目

若要追问这一路径是什么? 途经哪几个点?
只要回溯 ai(jk ) 是如何形成即可求得

例如 a1(7,3) 我们来看一下它的形成过程:
= A1(1)

(0 1 0 0 1 0 0)
15

A(2) 1



(0 1 0 0 1 0 0)×

15
= A A1(1) ×

A1(3) =

(1

0

0

10
154

1

0)×

= A(2) 1

×

A

0100100 0000000 0100011 1010101 1001010 0 0 1 0540 0 0 0000010

=(1 0 0 1 0 1 0)
154

0100100

0000000

0100011

1 0 1 0 1 0 1 = (1 1 2 0 2 0 1)

1 0 0 1 0 1 0 47

1547

0010000

0000010

5.4 Connectivity

【 Theorem 】设G是带有相对于顶点顺序v1, v2, . . . vn的邻接 矩阵A的图(允许带有向边或无向边,带多重边和环)。 从 vi到vj的长度为r的不同通路的数目等于Ar的第(i,j)项,其 中r是正整数。

Note: This is the standard power of A, not the Boolean product.

Proof:

Let
A ? (aij )n?n
(1) A aij ? 1
aij ? 0

(3)

(2A) r ?A(2cij )n?n

? A2A?r?1A?? AA?r ?(Abij?)n(?dn ,ijb)inj ??n n aik akj

k ?1

? adik aij kj??c1i1a?1 j

a?ik

c?i 2

aa2kjj

??1???(Vciin,Vankj)

??

En,

(Vcikk

,aVk

j j

)

?

E

bij: the number of different paths of length k2?1

from vi to vj

43 2019/9/14

〖Example 1〗 v5

v4 v1
v6

5.4 Connectivity
v2 v3

(1) How many paths of length 2 are there from v5 to v4? a54 in A2; 1
(2) The number of paths not exceeding 6 are there from v4 to v5? a45 in A+A2+A3+A4+A5+A6 ; 2
(3) The number of circuits starting at vertex v5 whose length is not exceeding 6?

44 2019/9/14

对图G=(V,E) 而言,若两顶点vi,vj 间存在路径,则称vi,vj 相连通;
无向图G中,若任意两点都连通,则称G为连通图(connected graph) ,否则为非连通图;
非连通图可分解为若干个连通子图(连通分量);
每个连通分量均有极大连通子图。

连通图

非连通图

5.4 Connectivity
Connectedness in undirected graphs 无向图的连通性
若无向图每一对不同的顶点之间都有通路,则该图称为连通的.

〖Example 2〗 Are the following graphs connected?

a b
e
d c
Yes.

b

a

e d c
No.

46 2019/9/14

5.4 Connectivity

【 Theorem 】 在连通无向图的每一对不同顶点之间都存在 简单通路
Proof:
Because the graph is connected there is a path between u and v. Throw out all redundant circuits to make the path simple.
因为图是连通的,是哟以u和v之间至少有1条通路。删除所有冗余的回路使得通路更短。

连通分支

For example,
a
b
47 2019/9/14

d e

c

f

i

h

g j

5.4 Connectivity
有时删除一个顶点和它所关联的边,就产生带有比原图更多的连通分支 的子图。把这样的顶点称为割点(或节点)。从连通图里删除割点,就 产生不连通的子图。 同理,把一旦删除就产生带有比原图更多的连通分支的子图的边称为割 边或桥
For example,
(1)
In the star network the center vertex is a cut vertex. All edges are cut edges.在星状网络中中心顶点是一个割点, 其中所有的边都是割边
48 2019/9/14

(2)

5.4 Connectivity

There are no cut edges or vertices in the graph G above. Removal of any vertex or edge does not create additional components.
49 2019/9/14

5.4 Connectivity
Connectedness in directed graphs 有向图的连通性
强连通的:若每当a和b都是一个有向图里的顶点时,就有从a到b和从b 到a的通路. 弱连通的:若在有向图的底图里,任何两个顶点之间都有通路 由定义可知:任何强连通有向图也是弱连通的。

For example,
50 2019/9/14

a b
d
c
Weakly connected

a b
d
c
Strongly connected

5.4 Connectivity
Paths and Isomorphism 通路与同构
Idea: (1) Some other invariants 一些其他的不变量
? The number and size of connected components 连通分支的 数目及其大小
? Path ? Two graphs are isomorphic only if they have simple circuits
of the same length. 两图同构只有当他们具有相同长度的简单回 路。 ? Two graphs are isomorphic only if they contain paths that go through vertices so that the corresponding vertices in the two graphs have the same degree. 应用两图中相应顶点具 有相同的度来判断两图的同构情况
(2) We can also use paths to find mapping that are potential isomorphisms.
51 2019/9/14

5.4 Connectivity
〖Example 3〗 Are these two graphs isomorphic?
Solution: No. Because the right graph contains circuits of length 3, while the left graph does not.
52 2019/9/14

Homework: P. 476 18(b,c), 20

5.4 Connectivity

53 2019/9/14

本节内容到此结束


相关文档

离散数学第四版3-5章课后习题答案
赵洪銮《离散数学》第五章3-4节
离散数学第4章(3)
新编文档-离散数学-第5章-3、4-精品文档
赵洪銮《离散数学》第五章3-4节-文档资料
赵洪銮《离散数学》第五章3-4节名师教学资料
离散数学4.1-4.3
2019赵洪銮《离散数学》第五章3-4节.ppt
离散数学3-4
电脑版