8.3 图的矩阵表示.ppt

第八章 图论
图的基本概念
路径和回路
图的矩阵表示
二部图

树

图的矩阵表示
1. 邻接矩阵
2. 可达性矩阵
3. 可达性矩阵的应用
4. 关联矩阵
1、邻接矩阵
定义1 设G=<V,E>有向（无向）线图，有n个标定了次序的结点v1, v2,…vnV，则n阶方阵A=(aij)称为G的邻接矩阵，这里
例1 左下图的邻接矩阵：
注① 图的邻接矩阵与n个结点的标定次序有关，对于V中各元素不同的标定次序，可得出不同的邻接矩阵。不过这些矩阵可以通过交换行和列而相互得出。具有这样性质的矩阵称它们置换等价。
例如，左下图的两个置换等价邻接矩阵：
② 有向简单图在标定次序后得到唯一邻接矩阵;
零图的邻接矩阵的元素全为0，称为零矩阵。
完全图Kn的邻接矩阵是恰有n个0并全在对角线上的n阶(0,1)方阵。
当有向线图代表关系，关系矩阵就是邻接矩阵。
有向线图G=V,E的邻接矩阵是A，则G的逆图G~=V,E~的邻接矩阵是A的转置矩阵，记为AT。
无向简单图的邻接矩阵是对称矩阵：A=AT。
有n个结点的赋权图G=V,E,W的邻接矩阵是n阶方阵A=(aij)，其中当(vi,vj)E，aij=W(vi,vj)；否则,aij=0。
有n个结点的多重图的邻接矩阵是n阶方阵A=(aij)，其中aij代表从vi到vj的边的重数。
几个特殊图的邻接矩阵
邻接矩阵的图论意义
设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于
结点的度。
邻接矩阵的图论意义
设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于
结点的度。
设A为有向简单图G的邻接矩阵。
① A的第i行(列)和等于第i个结点的出(入)度，i=1,…n。
v3的出度=1+1+0+1=3，v3的入度=0+1+0+0=1
邻接矩阵的图论意义
设A为无向简单图G的邻接矩阵，其第i行(列)元素为1的个数等于
结点的度。
设A为有向简单图G的邻接矩阵。
① A的第i行(列)和等于第i个结点的出(入)度，i=1,…n。
② B=AAT=(bij)的元素 bij=ai1aj1+…+ainajn=k
表示有k个点，都是从i,j引出的有向边的
公共交点。
特别地，bii是第i结点的出度。
对偶地
可讨论ATA的元素的图论意义。
i
j
练****求AAT，ATA，并由此求每个结点的出度与入度