第七章 离散数学 图论-3rd

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

离散数学大连理工大学软件学院陈志奎教授办公室：综合楼411,Tel: 87571525实验室：教学楼A318/A323,Tel:87571620/24 Mobile: 13478461921 Email: zkchen@http://www.77cn.com.cn zkchen00@http://www.77cn.com.cn

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

第七章图论

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

7.4图的矩阵表示一、邻接矩阵 V, E,定义：设 G=ψ 是一个简单有向图，其中的=结点集合V{v1, v2, vn},并且假定各结点已经有了从结点v1到vn的次序。试定义一个n×n的矩阵A,使得其中的元素

ai j={01

当 vi, v j ∈E当 vi, v j E

(1)

则称这样的矩阵A是图G的邻接矩阵。

3/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵定义：元素或为0或为1的任何矩阵，都称为比特矩阵或布尔矩阵。

邻接矩阵也是布尔矩阵，第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。

4/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵图的邻接矩阵不具有唯一性。 V, E,对于给定简单有向图G=ψ 来说，其邻接矩阵依赖于集合V中的各元素间的次序关系。

给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。

5/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵例：写出下图的邻接矩阵，并计算各个节点的出度和入度。解：首先给各结点安排好一个 v1次序，譬如说是v1, v2, v3, v4。得 v2出邻接矩阵如下：

v3

v4

v1 v 2 v1 0 0 v2 A1= v3 1 v4 1 1 0 1 1

v3 0 0 0 1

v4 0 1 0 0 6/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵v1v3 v2 v4上例中，如果重新把各结点排列成 v2, v3, v1, v4,就能写出另外一个矩阵如下：v2 v2 0 v3 1 A2= v1 1 v4 1 v 3 v1 v4 0 0 1 0 1 0 0 0 0 1 1 0

如果首先交换第一行和第三行，而后交换第一列与第三列，接着交换v2和v3所对应的行，而后交换v2和v3所对应的列，那么就能够由邻接矩阵A2求得邻接矩阵A1。7/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵 对于给定图G,显然不会因结点编序不同而使其结构会发生任何变化，即图的结点所有不同编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的n!个邻接矩阵都是相似的。 今后将略去这种由于V中结点编序而引起邻接矩阵的任意性。而取该图的任一个邻接矩阵作为该图的矩阵表示。

8/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵由邻接矩阵判断有向图的性质： 如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。 如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。 对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j

而言，都应有aij=aji。 如果给定有向图是反对称的，则对于所有的i和j和 i≠j而言，aij=1蕴含aji=0。

9/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵

可以把简单有向图的矩阵表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称的邻接矩阵，在多重边图或加权图的情况下，可以令 aij= wij其中的wij,或者是边 vi, v j 的重数，或者是边 vi, v j 的权。另外，若 vi, v j E,则 wij= 0。在零图的邻接矩阵中，所有元素都应该是0,亦即其邻接矩阵是个零矩阵。

10/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵逆图的邻接矩阵： V, E,如果给定的图G=ψ 是一个简单有向图，并且 其邻接矩阵是A,则图G的逆图的邻接矩阵 G是A的转置 AT。对于无向图或者对称的有向图来说，应有 AT= A。

11/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

B= AA

T

在图上的意义

定义矩阵 B= AAT。设 aij是邻接矩阵中的第i行和第j列上的 (i, j )元素，bij是矩阵中的第i行和第j列上的元=素(i,j)。于是，对于 i, j 1, 2,3, , n来说，有

bij=∑ aik a j kk 1

n

如果边 vi, vk ∈ E,则有 aik= 1,如果边 v j, vk ∈ E,则有 a jk= 1。对于某一个确定的k来说，如果 vi, vk 和 v j, vk 都是给定图的边，则在表示bij的上述求和表达式中，应该引入基值1。从结点 vi和vj二者引出的边，如果能共同终止于一些结点的话，那么这样的一些结点的数目，就是元素 bij的值。12/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

B= AA

T

在图上的意义 0 1 AT= 0 0 0 0 0 1 1 1 0 0 1 1 1 0

例：如图，求 AAT解： 0 1 0 0 0 0 0 1 A= 1 1 0 0 1 1 1 0

1 0 AAT= 1 1简单算法：

0 1 0 0

1 0 2 2

1 0 2 3

v1v3

v2 v4

原矩阵A中，第i行和第j行相交，有几个1,AAT的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的出度。13/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

C=A ATn

在图上的意义

设 aij是邻接矩阵A中的(i,j)元素； cij是矩阵C中的元=素。于是，对于i 1, 2, , n,

Cij=∑ aki akjk=1

对于某一个确定的k来说，如果 vk, vi , vk, v j 都是给定图的边，则在上式中应引入基值1。可得从图中的一些点所引出的边，如果能够同时终止于结点vi和vj的话，那么这样的一些结点的数目，就是元素Cij的值。

14/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

C=A AT

在图上的意义

例：如图，求 AT A解： 0 0 A= 1 1 1 0 1 1 0 0 0 1 0 0 1 T 1 A= 0 0 0 00 0 0 1 1 1 0 0 1 1 1 0

v1v3

v2 v4

2 2 1 0 简单算法： 2 3 1 0 原矩阵A中，第i列和第j AT A= 列相交，有几个1,ATA 1 1 1 0 的第i行第j列就是几。 0 0 0

1 矩阵的主对角线的元素对应了各个节点的入度。 15/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵的幂=对于 n 2,3, 4, 来说，考察邻接矩阵A的幂An可知，邻接矩阵A中的第i行和第j列上的元素值1,说明了图 G中存在一条边<vi,vj>,也就是说，存在一条从结点 vi到vj长度为1的路径。试定义矩阵A2,使得A2中的各 aij (2)为元素

aij (2)=∑ aik akjk=1

n

aij (2)等于从vi到vj长度为2的不同路径的元素值 (2)数目。显然，矩阵中主对角线上的元素 aii的 (i值，表示了结点vi= 1, 2, , n)上长度为2的循环

的个数。矩阵A3中的元素值(i,j)依次类推。16/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵的幂例：

v1v3

v2 v4 1 1 3 A= 1 1 1 2 1 2 1 0 1 1

0 1 2 A= 0 1

0 1 0 2

0 1 0 0

1 0 1 1 2 2 2 4 0 1 0 2 1 2 1 2 17/41

1 0 1 4 1 A= 1 0 3 2

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵的幂 V, E,定理：设G=ψ 是一简单有向图，并且A是G的邻=接矩阵。对于 m 1, 2,3, 来说，矩阵Am中的元素(i,j)的值，等于从vi到vj长度为m的路径数目。

证：对于m进行归纳证明。当m=1时，由邻接矩阵的定义中能够得到Am=A。设矩阵Ak中的元素(i,j)值 aij ( k ),且对于m=k来说结论为真。因为 Ak+1= Ak A,是 n所以应有 ( k+1) (k )aij=∑ aik akjk=1

为k+1的各条路径的数目。这里vk是倒数第二个 aij ( k+1)应是从结点vi出发，经过任意结点。因此，的倒数第二个结点到vj的长度为k+1的路径总数。因此，对于m=k+1,定理成立。18/41

aik ( k ) akj是从结点v出发，经过结点v到v的长度 i k j

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

邻接矩阵的幂根据上述定理，可得出结论：

能使矩阵Am中的元素(i,j)值是非零的最小正整数m, d vi。j ,v就是距离

m 对于= 1, 2, , n 1和i≠ j来说，如果矩阵 Am中的(i,j)元素值和(j,i)元素值都为0,那么就不会有任何路径连通结点vi和vj。因此，结点vi和vj必定是属于图G的不同分图。

19/41

本文来源：https://www.bwwdw.com/article/sf8i.html