图的表示和图同构VIP免费

图的表示与图同构离散数学─图论初步南京大学计算机科学与技术系内容提要图的表示邻接矩阵的运算图的同构图的表示关联矩阵邻接矩阵邻接表关联矩阵(incidencematrix)无向图G=(V,E,)，不妨设V＝v1，…，vn，E＝e1…，，em。M(G)＝mij称为G的关联矩阵(n×m阶矩阵),其中无向图G可以是伪图（含自环或多重边）。否则关联如果0ve1mijijvi(ej)举例（关联矩阵）01100101100001111001M(G)v1v2v3v4e1e2e3e4e5关联矩阵表示法不适合于有向图邻接矩阵(adjacencymatrix)简单有向图G=(V,E,)，设V＝v1，…，vn，E＝e1…，，em。A(G)＝aij称为G的邻接矩阵(n×n阶矩阵)，其中否则邻接到如果0vv1ajiijeE.(e)=(vi,vj)举例（邻接矩阵）0001101111000010A(G)v1v2v3v4可推广到简单无向图举例（邻接矩阵）0101101101011110A(G)v1v2v3v4简单无向图的邻接矩阵是对称矩阵邻接表若图G=(V,E,)没有多重边，列出这个图的所有边。对每个顶点，列出与其邻接的顶点。是单射顶点相邻顶点ab,c,ebaca,d,edc,eea,c,dacbed邻接表（有向图）若图G=(V,E,)没有多重边，列出这个图的所有边。对每个顶点，列出与其邻接的顶点。是单射顶点相邻顶点ab,c,d,ebb,dca,c,edeb,c,dacbed关于邻接矩阵通常，邻接矩阵中的元素为0和1，称为布尔矩阵。邻接矩阵也可表示包含多重边的图，此时的矩阵不是布尔矩阵。v1v2v3v40212211011032030A关于邻接矩阵当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵。无向图的邻接矩阵是对称的。图G的邻接矩阵中的元素的次序是无关紧要的，行与行、列与列进行相应交换，则可得到相同的矩阵。若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵行与行、列与列之间的相应交换后得到和另一矩阵相同的矩阵，则此二图同构。邻接矩阵的运算顶点的度行中1的个数就是行中相应结点的出度列中1的个数就是列中相应结点的入度Deg+(1)=1,Deg-(1)=2Deg+(2)=2,Deg-(2)=2Deg+(3)=3,Deg-(3)=1Deg+(4)=1,Deg-(4)=20001101111000010Av1v2v3v4邻接矩阵的运算逆图（转置矩阵）设Ｇ的邻接矩阵为A，则G的逆图的邻接矩阵是A的转置矩阵，用AT表示。１０００１１０１００１１０１００A０１１００１００１０１０００１１TAjninjijinkjkikijijTaaaaaaaabbBAA22111][bij表示结点i和结点j均有边指向的那些结点的个数；若i＝j，则bii表示结点i的出度。邻接矩阵的运算njnijijinkkjkiijijTaaaaaaaaCCCAA22111][Cij表示同时有边指向结点i和结点j的那些结点的个数；若i＝j，则Cii表示结点i的入度。邻接矩阵的运算００１１１１３１０２１０１０１０TAA１１１２００１１１２０１２１０１AAT0001101111000010Av1v2v3v4邻接矩阵的运算nknjinjikjikijijaaaaaaddDAAA1112][若aik×akj＝1，则表示有i→k→j长度为2的有向边；dij表示i和j之间具有长度为2的通路个数。邻接矩阵的运算０１００１１１１２１０１００１１AAA2００１１２２１２１２１１２１０１AAA23邻接矩阵的运算0001101111000010Av1v2v3v4从v2→v1，有二条长度为2的通路；有一条长度为3的通路３２１２７７４７５５４６３４２３43214AAAAB长度不大于k的通路个数邻接矩阵的运算0001101111000010Av1v2v3v4图的同构图同构的定义设G1=(V1,E1,1)和G2=(V2,E2,2)是两个简单无向图。若存在双射f:V1V2,u和v在G1中相邻当且仅当f(u)和f(v)在G2中相邻。此时称f是一个同构函...