graph-chapter6图的矩阵表示.ppt

第六章图的矩阵表示计算机科学领域有许多算法涉及图。计算机存储图计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格,一般用大写字母表示。(元素、组成的矩阵表格,一般用大写字母表示。(元素、行、列)。图论有效地利用了矩阵,将其作为表达行、列)。图论有效地利用了矩阵,将其作为表达图及其性质的有效工具和手段。图及其性质的有效工具和手段。 关联矩阵定义 设图 G为( p,q ) 1, 0, ij j i m ????若边与顶点关联否则则由元素构成的矩阵为图 G的完全关联矩阵,记作。 ijm p q ? eM v v 2 2v v 1 1e e 3 3e e 4 4e e 2 2e e 1 11100V 30111v 21011v 1e 4e 3e 2e 1 v3 v3 定理 阶连通图 G的完全关联矩阵的秩为 p-1 。定理 图G的完全关联矩阵的秩等于 G的秩 R(G)。定理 p 阶图 G是连通的当且仅当 G的完全关联矩阵的秩为 p-1 。定义 在p阶连通图 G的完全关联矩阵 M e中,划去任一行后所得到的( p-1 )×q矩阵,称为图 G的关联矩阵, 记作 M ,划去的行所对应的顶点称为参考点。定义 p×q矩阵的一个阶为 min ( p,q )的方阵,称为p×q矩阵的一个大子阵,大子阵定义的行列式称为大行列式。定理 连通图 G的关联矩阵 M的一个大子阵是非奇异的充要条件为与这个大子阵的列相应的边组成 G的一棵生成树。?一个图的生成树与关联矩阵的非奇异大子阵存在一一对应的关系。?一个连通图的关联矩阵一定存在非奇异的大子阵,因此一个连通图一定存在生成树。?求连通图全部生成树的方法:找出图 G的关联矩阵 M的全部非奇异大子阵,每个大子阵的列所对应的边就组成 G的一棵生成树。 v v 2 2v v 1 1e e 3 3e e 4 4e e 2 2e e 1 11100V 30111v 21011v 1e 4e 3e 2e 1 v3 v3 圈矩阵定义 设连通( p,q )图G,令 1, 0, ij j i b ????若边在环路中否则则由元素构成的矩阵为图 G的完全圈矩阵,记作。 1 ( 1, 2, , 2 1, 1, 2, , ) q p ij b i j q ? ?? ??? ? 1 (2 1) q pq ? ?? ? eB完全圈矩阵 v v 2 2v v 1 1e e 3 3e e 4 4e e 2 2e e 1 1 v3 v3