离散数学-图的矩阵表示

设有向图G的结点集合 ，它的邻接矩阵 为 ，现在我们想计算从结点 到 结点 的 长度为2的路的数目
分析：从 到 长度为2的路，中间必须经过 如果图G 中有路 存在，则肯定有 ，反之如果 图G中不存在路 ，那么 或者 ，即 于是从结点 到 的长度为2的路的数目就 等于：
按照矩阵的乘法规则，上式恰好等于矩阵 的元素，即 表示从 到 ； 的长度为2的路的数目
中第i行，第j列
考虑从vi到v j的长度为3的路的数目，可以看作是由vi到vk的长度为1的路，再 联结vk 到v j的长度为2的路，则类似可知从vi到v j的长度为3的路的数目为： a
( 3) ij ( 2) aik akj ，即为( A(G )) 3的第i行，第j列元素。 k 1 n
行相加运算： 有向图：对应分量普通加法运算； 无向图：对应分量模2加法运算。 行相加相当于G中对应结点的合并。 air a jr 1 ，说明v 和v 中只有一个结点是边e 的端点，合并 i j r 后仍是er的端点。
air a jr 0 ，有两种情况：
a、vi，vj都不是er的端点； b、vi，vj都是er的端点，合并后删去自回路。 若合并后完全关联矩阵中出现元素全为0的列，表明对应的 边消失。 有了这种运算，就可以运用这种运算求关联矩阵的秩
1 0 1 0
0 1 0 0
0 1 ，求G的可达性矩阵。 1 0
Байду номын сангаас
0 2 A2 1 0
0 1 1 1
1 0 1 0
1 1 1 0
2 1 A3 2 0
4 5 7 2 2 4 4 1
1 2 2 0
3 6 7 2
0 1 1 1
由前面的定理7-2.1的推论可知，如果在vi到vj之间存在路，必定存在 一条长度不超过n的通路，所以l只需计算到n就可以了。
推论： G有n个结点， A是邻接矩阵， Bn A A2 An，bij 为Bn的i行，j列元素，若bij>0，则表明vi，vj中存在路。 对于简单有向图的任意两个结点之间的可达性，也可以用矩阵 表示出来，即可达性矩阵
例：计算右图对应的完全关联矩阵的秩。
v4 e1 v5
e2 e3
v3 e4 e5 e6 e7 v1 v2
推论： G有r个结点，w个极大连通子图，则图G的完全关联 矩阵的秩为r-w。 可用之求图的最大连通子图数目。
谢谢
矩阵的秩：矩阵中所有非零子式的最高阶数；就是将矩阵 通过初等变换化为行阶梯后非零行的行数。
定理： G为连通图，有r个结点，则其完全关联矩阵M(G)的秩为 r-1，即rank M(G)=r-1。 证明：对无向图，用数学归纳法 （ 1 ）r 1， 2，显然； （2）假设r 1时成立。即连通图G有r 1个结点，则rank M (G ) r 2 （3）证明结点数为r时成立 设M（G）的第一列对应边e，e的端点为vi 和v j，调整行使得第i行成为
第一行，则M（G）首列仅第一行和第j行为1，将第一行加到第j行，得
1 0 ，M (G1 )是G1的完全关联矩阵，而G1是G M （G） M (G1 ) 0 合并vi 和v j 得到的，G是连通图，则G1也是连通图，所以rank M (G1 ) r 2 rank M (G ) rank M (G ) 1 rank M (G1 ) r 1
e4
e3 v4
e6
v2
e2
v3
有向图的完全 关联矩阵也有类似于无向图的一些性质
（1）M（G）中每一列中有且仅有两个1， 对应图中每一边关联两个结点。 （2）每一行中元素的和为对应结点的度数。 （3）一行中若元素全为0，则其对应的结 点为孤立结点。 （4）平行边对应的列相同。 （5）结点或边编序不同，对应完全关联矩 阵只有行序、列序的差别。 （1）每一列中一个值为1，一个为-1， 对应图中的一条有向边。 （2）把一行中的值为1的元素相加，得 到顶点的出度，把值为-1的元素相加， 得到顶点的入度。 （3）一行中元素全为0，对应孤立结点。 （4）平行边对应的列相同。 （5）结点或边编序不同，对应完全关联 矩阵只有行序、列序的差别。
1 1 2 1 A4 2 3 1 2
1 1 P 1 1
2 2 3 1
1 1 1 1 1 1 1 1
1 2 2 0
1 1 1 1
1 3 3 1
3 5 B4 A A1 A2 A3 A4 7 3
v1 e1 e2 e6 e3 v3
1 2 3 4 5 6
e5 v4
v2 v5
e4
v1 v2 v3 v4 v5
1 1 0 0 0
1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0
1 0 1 0 0
从关联矩阵中看出图形的一些性质：
（1）M（G）中每一列中有且仅有两个1，对应图中每一边关联两 个结点。 （2）每一行中元素的和为对应结点的度数。 （3）一行中若元素全为0，则其对应的结点为孤立结点。 （4）平行边对应的列相同。 （5）结点或边编序不同，对应完全关联矩阵只有行序、列序的 差别。 类似，给出有向图的完全关联矩阵的定义： v1 e1 （b）G为有向图 G=<V,E>， ，e1 e2 e3 e4 e5 e6 v1 1 1 0 0 1 1 e2 v2 pX q 阶矩阵 M(G)=(m ) 为 G 的完全关联矩阵，其中： ij e v
2、可达性矩阵： G=<V,E>是简单有向图，|V|=n，定义nxn矩阵 P=(pij)为可达性矩阵，其中
1 pij 0 从vi到v j 存在路 从vi到v j 不存在路
将Bn中不为零的元素值改为1，就可得到可达性矩阵P。
例1： 解：
0 0 设图G的邻接矩阵为A 1 1
图的矩阵表示
对于给定集合A上的关系R，可以用有向图来表示，而对于关 1. 邻接矩阵： 系图，又可以用一个矩阵表示，所以对于一般形式的图，也 给出其矩阵表示。 V {v , v ,, v } 是G的n个结点， • 设G=<V,E>是一个简单图，
1 2 n
则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中：
5
e6
v4
e4
mij v －1 3 0
e3 1 v5
vi是e j的起点 vi是e j的终点 若vi不关联e j
2
v3 v4 v5
1 0 0 0
1 0 0 0
1 1 0 0
0 1 1 0
0 0 1 0
0 1 0 0
例
e1
v1
e5
e7
v5
关联矩阵：
e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v4 v5 1 0 -1 1 0 -1 0 0 0 0 0 0 1 -1 0 0 0 0 1 -1 1 0 0 0 -1 1 0 -1 0 0 1 0 0 -1 0
由归纳假设法可得下面定理。
定理： A(G)是图G的邻接矩阵，则(A(G))l中的i行，j列元素 aij(l)等于G中联结vi与vj的长度为l的路的数目。
证明：用数学归纳法 当l=2时，由上面证明知显然成立
假设命题对l成立，只需证明当l=l+1时也成立即可 由 所以
在实际问题中，常需要考虑到结点之间是否存在路的问题。 2 n l 可以通过计算A,A ,...,A ,...，当发现某个A 的第i行,第j列不为0， 就表明vi到vj可达。
1 aij 0
v1
v2
vi vi
adjvj nadjvj或i j
adj表是邻接，nadj表示不邻接。
v5
v3
v4
简单图是无向图，邻接矩阵是对称的； 简单图是有向图时，邻接矩阵不一定对称。
在邻接矩阵A中，第i行中值为1的元素个数等于vi的出度； 第j列中值为1的元素个数等于vj的入度。 零矩阵对应零图；(仅有孤立结点组成的图称为零图)
对于无向图，邻接矩阵是一个对称矩阵，其可达性矩阵也是对称的。
上面我们介绍了图的邻接矩阵表示和可达性矩阵表示，可知 这两种表示方法都是跟结点相关的。 还可以给出结点和边的关联矩阵，在给出点和边的关联关系 时，假定图中无自回路。下面给出完全关联矩阵的概念。
3、完全关联矩阵：
E {e1 , e2 ,, eq } （a）G为无向图 设 V {v1, v2 ,, v p } 为G的结点集， 为G的边集，称矩阵M(G)=(mij)为完全关联矩阵，其中： 若vi关联e j 1 mij 若vi不关联e j 0 完全关联矩阵为： 例： e e e e e e