《图的代数表示及其特征.ppt》由会员分享，可在线阅读，更多相关《图的代数表示及其特征.ppt（16页珍藏版）》请在三一文库上搜索。
1、1.5 图的代数表示及其特征,邻接矩阵 点与点的关系,对称矩阵,每一行、列之和为该顶点的度,简单图,An 中元素的含义: 边数为n的途径数,推论：若A为简单图G 的邻接矩阵，则 1）A2 中对角线上元素为顶点的度； 2） A3中对角线上元素为含该顶点的 三角形数目的两倍。,思考？ 如何从 An中寻找任意两点间的距离？,推广的邻接矩阵（复合图）,无环图,对称矩阵,每一行、列之和为该顶点的度,An 中元素的含义 边数为n的途径数,推论：若A为简单图G 的邻接矩阵，则 1）A2 中对角线上元素为顶点的度； 2） A3中对角线上元素为含该顶点的 三角形数目的两倍。,思考？ 如何从 An中寻找任意两点间
2、的距离？,思考？ 上述结论对无环图成立吗？,推广的邻接矩阵（复合图）续。,有环图,对称矩阵,每一行、列之和不一定为该顶点的度,An 中元素的含义 边数为n的途径数,邻接矩阵的进一步推广有向图,每一行之和为该顶点的出度,每一列之和为该顶点的入度,An 中元素的含义 边数为n的途径数,推论：若A为简单图G 的邻接矩阵，则 1）A2 中对角线上元素为顶点的度； 2） A3中对角线上元素为含该顶点的 三角形数目的两倍。,思考？ 如何从 An中寻找任意两点间的距离？,思考？ 上述结论对有向图成立吗？,无向 有向图,无向 有向图,思考？ 邻接矩阵A所对应的图G是什么？,每一列之和为2,关联矩阵 点与边的关系,定理：具有n个顶点的连通图的关联矩阵的秩为n-1,图表示法和矩阵表示法是同一问题的两种不同表示方法，两者之间是等价的。,