P称为图G的可达性矩阵。
方法① 利用矩阵Bn（Bn-1）确定P： 当bij=0时，pij=0；否则，pij=1。
方法② 直接由邻接矩阵确定可达矩阵： P=A∨A2∨…∨An，
其中Ak为A的布尔方幂。
计算可达矩阵举例：
0 1 0 1
0 0 1 1
1 1 0 1
0 1 1 2
A
0
1
0
1
1
A (2)
1
1 0 1
0
1 1
0 1
1
A (3)
0
2
1
1 1
1 1
2
2
A ( 4 ) 1 1
1 2
1 1
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
方法1：先由邻接矩阵A求B4， B4=A+A(2)+A(3)+A(4) 然后写出可达矩阵P。
1325 1111 B4 32533386 P11111111
0
0
1
0
1
v1
0 0 0 1 0
0 0 1 1 1
0 0 1 1 1 P A A2 A3 A4 A5 0 0 1 1 1
0 0 1 1 1
0 0 1 1 1
3.可达矩阵的应用
利用一个图的可达性矩阵，求出这个图的所有强分图。 方法：图G的强分图可从矩阵P∧PT求得
0 0 0 0 0
0 1 0 1
A
0
0 11
0 1 0 1
0
1
0
0
0 1 11
A (2)
0
2
0
1
0 1 11
0
0
1
1
0 2 1 2
A (3)
0
1
2
2
0 2 1 2
0
2
0
1
0 3 2 3
A (4)
0
41
3
0 3 2 3
0
1
2
2
作业
P284 1 P285 3(+关联矩阵)
0 0 3 7 3
2、可达性矩阵
有向图G中从vi到vj是否有路可达可通过矩阵运算而得到。
定义2 设G=<V,E>为简单有向图，V={v1,v2,…vn}，定义矩阵 P=(pij)，其中 pij 1 0从 从 v v ii到 到 v vj至 j不 少 存 存 在 在 一 一 条 条 非 非 零 零 长 长 度 度 的 的 路 路 径 径
离散数学
电子课件
南京信息工程大学 离散数学教学组 制作
第八章 图论
8.1 图的基本概念 8.2 路径和回路 8.3 图的矩阵表示 8.4 二部图 8.5 平面图 8.6 树 8.7 有向树
8.3 图的矩阵表示
1. 邻接矩阵 2. 可达性矩阵 3. 可达性矩阵的应用 4. 关联矩阵
1、邻接矩阵
定义1 设G=<V,E>有向（无向）线图，有n个标定了次序的结 点v1, v2,…vnV，则n阶方阵A=(aij)称为G的邻接矩阵，这里
0 1 0 0
A
0
0
1
1
1 1 0 1
1
0
0
0
v3的出度=1+1+0+1=3，v3的入度=0+1+0+0=1
邻接矩阵的图论意义
设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于
结点的度。
设A为有向简单图G的邻接矩阵。
① A的第i行(列)和等于第i个结点的出(入)度，i=1,…n。
0
0
0Hale Waihona Puke 0 0 1 1AT
1
0
1
0
0 1 0 0
0
1
1
0
1 0 1 0
2 1 0 1
AAT
0
1
2 1
1 3
0
1
AT
A
1
0
2 0
0 1
1
1
0
0
1
1
1
1
1
2
练习：求AAT，ATA，并由此求每个结点的出度与入度
0 1 0 0
A
0
0
1
1
1 1 0 1
1
0
0
0
0 0 1 1
AT
④ Br=A+A(2)+A(3)+…+A(r)的元素bij表示从vi到vj长度小于等于r的 不同路径总数。
在n个结点的简单有向图中，基本路径长度不超过n-1，基本回路
长度不超过n，故可用
Bn-1=A+A(2)+A(3)+…+A(n-1) (ij时) Bn=A+A(2)+A(3)+…+A(n) (i=j时)
0 0 0 0 0
P PT
0
0
1
1
1
.
0 0 1 1 1
0
0
1
1
1
可求得G的强连通分支对应结点集为： {1}，{2}，{3,4,5}。
4 关联矩阵
定义3 设G=<V,E>是无向图，V={v1,v2…，vn}，E={e1,e2…,en}， 一个n×m矩阵M=(mij)称为G的关联矩阵，其中mij是结点vi和ej的 关联次数。 定义4 设G=<V,E>是有向简单图，V={v1,v2…，vn}，E={e1,e2…, en}，一个n×m矩阵M=(mij)称为G的关联矩阵，其中
② 有向简单图在标定次序后得到唯一邻接矩阵;
例如，左下图的两个置换等价邻接矩阵：
0 1 0 0
A
0
0
1
1
1 1 0 1
1
0
0
0
v2 v3 v1 v4
v
2
0
1
0
1
v
3
1
0
1
1
v1 1 0 0 0
v4 0 0 1 0
几个特殊图的邻接矩阵
• 零图的邻接矩阵的元素全为0，称为零矩阵。
A
0
0
1
1
1 1 0 1
1
0
0
0
0 0 1 1
A (2)
2
1
0
1
1 1 1 1
0
1
0
0
例 A(2)中的第2行第1列元素等于2，说明从v2到v1长度为2的 路的有两条： v2 v4 v1 ， v2 v3 v1 。
分析: a21(2)= a21a11+a22a21+ a23a31+a24a41=0•0+0•0+1•1+1•1=2 注意从v2到v1长度为2的路中间必经由一个结点vk,即v2 vk v1(1k4)。 一般地, A(m)中从i到j长为m的路径总数是aij(m)条，过i的长为m 的回路共有aii(m)条。
1 mij 0
vi是ej的始点 vi与ej不关联
1 vi是ej的终点
5、课堂练习
练习 求如下有向图的邻接矩阵A，指出从v1到v4且长度为 2和4的路。
解：从v1到v4长度为2的路有1条： v1v2v4 从v1到v4长度为4的路有3条： v1v2v4v2v4， v1v2v3v2v4，
v1v4v2v3v4
0
0
2
0
2
0
0
0
4
0
0 0 0 2 0
0 0 2 0 2
0 0 2 0 2
0
0
0
4
0
A(5) 0 0 0 4 0
v1
0
0
4
0
4
0 0 0 4 0
0 0 5 3 3
0
0
3
7
3
B5 A A(2) A(3) A(4) A(5) 0 0 3 7 3
0
0
7
6
7
② B=AAT=(bij)的元素 bij=ai1aj1+…+ainajn=k 表示有k个点，都是从i,j引出的有向边的
公共交点。
特别地，bii是第i结点的出度。
对偶地
可讨论ATA的元素的图论意义。
i
j
练习：求AAT，ATA，并由此求每个结点的出度与入度
0 1 0 0
A
0
0
1
1
1 1 0 1
1
研究vi到vj的可达性和经vi是否存在回路的问题。bij0(ij)表示从 vi到vj可达，否则从vi到vj不可达，分属不同强分图。bij 0(i=j)表 示经vi存在回路，否则表示不存在经vi的回路。
例2 根据有向图和矩阵B5，验证 (a) b52=0，所以v2和v5分属两个强分图。 (b) b11=0，所以没有经过v1的回路。 (c) b53=3，所以从v5到v3长度不超过5的路径有3条。
• 有n个结点的多重图的邻接矩阵是n阶方阵A=(aij)，其中aij代表 从vi到vj的边的重数。
邻接矩阵的图论意义
设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于 结点的度。
邻接矩阵的图论意义
设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于 结点的度。 设A为有向简单图G的邻接矩阵。 ① A的第i行(列)和等于第i个结点的出(入)度，i=1,…n。
v1
v1
0 0 1 0 0
0
0
0
1
0
A 0 0 0 1 0