文档介绍：关于图的矩阵表示
第1页，讲稿共91张，创作于星期日
图的矩阵表示
由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合V时结点的顺序。
用图形表示图是图论的一种为该图的矩阵表示。
第12页，讲稿共91张，创作于星期日
课堂练****1
1、写出下图所示无向图的完全关联矩阵
v2
v3
e2
v4
e5
e4
e3
e1
v1
第13页，讲稿共91张，创作于星期日
有向图的关联矩阵
定义 给定简单有向图D=<V,E>， V={v1, v2, …, vp}, E={e1, e2, …, eq}, p×q阶矩阵M(D)=(mij) p×q，其中
称M(G)为D的完全关联矩阵。
第14页，讲稿共91张，创作于星期日
v1
v2
v3
v4
e6
e1
e2
e3
e5
e4
第15页，讲稿共91张，创作于星期日
例 求下图的完全关联矩阵
e1
e2
e3
e4
e5
e6
e7
v1
1
0
0
0
1
1
1
v2
-1
1
0
0
0
0
0
v3
0
-1
1
0
0
-1
0
v4
0
0
-1
1
0
0
-1
v5
0
0
0
-1
-1
0
0
第16页，讲稿共91张，创作于星期日
有向图的完全关联矩阵的性质
(4) 平行边对应的列相同。
(5) 不能表示自环。
第17页，讲稿共91张，创作于星期日
v2
v3
e2
v4
e5
e4
e3
e1
v1
第18页，讲稿共91张，创作于星期日
完全关联矩阵的秩
定理 如果连通图G有p个顶点，则其完全关联矩阵的秩为p-1，即rank M(G)=p-1。
证明 对无向图进行证明
(1) 因为M(G)中的每一列只有两个1，若把M(G)的其余所有行加到最后一行上，则最后一行全为0（模2的运算，相当于各点邻集的环合），故rank M(G) ≤p-1。
第19页，讲稿共91张，创作于星期日
(2) 应用行变换使得M(G)第1列（边e）中的1个非零元在第1行第1列的位置，然后把第1行加到第1列另一个非零元所在行上，使得第1列中只有在首行上为1，其余全为0，得到矩阵M’(G)。
第20页，讲稿共91张，创作于星期日
v2
v3
e2
v4
e5
e4
e3
e1
v1
v3
v4
e2 e5
e4
e3
V1,v2
第21页，讲稿共91张，创作于星期日
由于G1是将M(G)的第1行与另一个首个元素为1的行加起来，对应的是将图的两个顶点放在一起，因此G1必是连通图，所以M’(G1)中没有全零行。若M’(G1)的第1列全零，则将M’(G1)中的非零列与它对换，然后再用交换行和一行加到另一行，使M’(G1)中第1列首元素为1，其余元素为零，得到M’’(G) ，如图所示
第22页，讲稿共91张，创作于星期日
第23页，讲稿共91张，创作于星期日
继续上述过程，并不改变矩阵秩，最终在经过p-1次，将M(G)变换成M(p-1)(G)，如上图所示,显然rank M(G)=rank M(p-1)(G) ≥p-1。综上所述，有rank M(G)=p-1。
第24页，讲稿共91张，创作于星期日
例 计算完全关联矩阵M(G)的秩。
e1
e2
e3
e4
e5
e6
e7
v1
0
0
0
0
0
1
1
v2
0
0
0
1
1
1
0
v3
0
1
1
1
0
0
0
v4
1
1
0
0
0
0
0
v5
1
0
1
0
1
0
1
(4)
(1)
第25页，讲稿共91张，创作于星期日
(1) (5)
(2)
(3)
(2) (5)
(
3
)
(
4
)
第26页，讲稿共91张，创作于星期日
(3) (5)
(
4
)
(
6
)
(4) (5)
这个矩阵的秩为4，
即rank M(G)=5-1=4。
第27页，讲稿共91张，创作于星期日
推论
推论 设图G有p个结点，k个连通分支，则图G完全关联矩阵的秩为p-k。
证明 设图G有p个结点，k个连通分支，则通过对M(G)进行行交换和列交换，总能得到如下分块矩阵。
第28页，讲稿共91张，创作于星期日
其中M(Gi)是连通子图Gi的关联矩阵，其对应的结点个