文档介绍：图的矩阵表示
图的矩阵表示
由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合V时结点的顺序。
用图形表示图是图论的一种表示方法。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。
在学****中常常需要分析图并在图上执行各种过程和算法，也许必须用计算机来执行这些算法，因此必须把图的结点和边传输给计算机，由于集合与图形都不适合计算机处理，所以要找到一种新的表示图的方法，这就是图的矩阵表示。利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。
第六章 图的矩阵表示
一个图可以按定义描述出来，也可以用图形表示出来，还可以同二元关系一样，用矩阵来表示。图用矩阵表示有很多优点，既便于利用代表知识研究图的性质、构造算法，也便于计算机处理。
图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，需将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。
*
本章的教学内容
关联矩阵
圈矩阵
割集矩阵
图的邻接矩阵
图的矩阵表示
计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。
无向图的完全关联矩阵
定义 给定无向图G，令v1, v2, …, vp, e1, e2, …, eq分别记为M(G)的顶点和边，则矩阵M(G)=(mij) p×q，其中
称M(G)为图G的完全关联矩阵。
例 下图G的完全关联矩阵为：
v1
v2
v3
v4
v5
e1
e2
e3
e4
实例1
例1 求下图的完全关联矩阵。
e1
e2
e3
e4
e5
e6
v1
1
1
0
0
1
1
v2
1
1
1
0
0
0
v3
0
0
1
1
0
1
v4
0
0
0
1
1
0
v5
0
0
0
0
0
0
无向图的完全关联矩阵有下列性质：
（1）M(G)中每列恰有两个1，即每条边与两个顶点关联；
（2）每一行元素之和等于对应顶点的度数；
（3）M(G)中元素之和等于G中顶点的度数总和；
（4）多重边对应的列相同；
（5）若G有w个连通分支G1, G2,⋯,Gw, 则有准分块对角阵
e5
e4
e3
e2
e1
e6
v5
v1
v4
v3
v2