三、图的矩阵表示

三、图的矩阵表示

用矩阵表示图对研究图的性质及应用常常是比较方便的,图的矩阵表示方法有多种,下面介绍两种重要的矩阵:邻接矩阵和边权矩阵.

img

网络(赋权图)G=(V,E),边(vi,vj)有权wij,构造矩阵A=(aijn×n,其中:当(vi,vj)∈E时aij=wij,否则为0,则称矩阵A为网络G的边权矩阵;网络图G=(V,E)中,img,构造一个矩阵A=(aijn×n,其中:当(vi,vj)∈E时aij=1,否则为0;称A为图G的邻接矩阵.

例4 分别求下列两个网络图(图9-7、图9-8)的邻接矩阵和边权矩阵.

img

图9-7

img

图9-8

img