5图论 矩阵表示9 28.ppt

3、有向图的邻接矩阵 定义：设有向图D＝V，E，V＝{v1，v2，…，vn}，E＝{e1，e2，…，em} 令aij为顶点vi邻接到顶点vj边的条数，称(aij)nxn为D的邻接矩阵，记作A(D)，或简记为A． 2）邻接矩阵的性质 （1）每列元素之和为结点的入度，即 ∑aij ＝ d+(vi)，i＝1，2，…，n， 所有列的和 ∑∑aij ＝ ∑d+(vi) ＝ m ，等于边数 每行元素之和为结点的出度，所有行的和也等于边数 （2）邻接矩阵中元素 aij 反映了有向图中结点vi到vj通路长度为1 (边)的条数 主对角线上元素反映了有向图中结点到自身的环（回路）的条数 （3）A(D)中所有元素之和为D中长度为1 (边)的通路总条数 主对角线的元素之和值为图中所有长度为1 的环的条数 要利用A(D)计算出D中长度为L(2,3,4..)的通路数和回路数 就需要用到邻接矩阵的幂次运算 （4）A2中的元素值bij是结点vi到vj长度为2 的通路条数： 说明：由矩阵的乘积定义 bij = ∑k aik * akj A3矩阵中的Cij元素值，表示了vi到vj长度为3 的通路条数。 （5）定理：设A为有向图D的邻接矩阵，V＝{v1，v2，…，vn} 为D的顶点集， 则A的L次幂AL(L≥1)中元素cij为D中vi到vj长度为L的通路数 其中cii为vi到自身长度为L的回路数 ∑∑cij(所有元素之和)为D中长度为L的通路总数， 其中 ∑cii为D中长度为L的回路总数． 推论 设BL＝A + A2十…+AL (L≥1)， 则BL中元素 bij为D中长度小于或等于L的通路数， 其中主对角线上元素值为D中长度小于或等于L的回路数 例：确定D中 1）v1到v4长度分别为1，2，3，4的通路有几条？ 2） v1到v4长度小于等于3的通路有几条？ 3） v1到自身长度分别为1，2，3，4的回路有几条？ 4） v4到自身长度小于等于3的回路有几条？ 5） 长度等于4的通路（不含回路）有几条？ 6） 长度等于4的回路有几条？ 7） 长度小于等于4的通路有几条？其中有几条是回路？ 4、有向图的可达矩阵 1）定义：设D＝V，E为有向图, V＝{v1，v2，…，vn} 令 1 vi可达vi pij ＝ 0 否则 称(pij)nxn为D的可达矩阵，记作P(D)，简记为P 2）可达矩阵的性质 （1）主对角线元素均为1 （每个结点自身可达） （2）可通过图的邻接矩阵A的n-1次幂Bn-1得到（将其非零元素均设为1即可） 4、有向图的可达矩阵 1）定义：设D＝V，E为有向图, V＝{v1，v2，…，vn} 令 1 vi可达vi pij ＝ 0 否则 称(pij)nxn为D的可达矩阵，记作P(D)，简记为P 作业： P294 44、45、46、47 例：给定有向图D，4个顶点7条边 邻接矩阵为 判定哈密顿图、半哈密顿图的充分条件： 定理15.7 设G是n阶无向简单图，若对于G中任意不相邻的结点u，v均有 d(u)+d(v)=n-1 则G中存在哈密顿通路 推论 设G是n（≥3)阶无向简单图，若对于G中任意不相邻的结点u，v均有 d(u)+d(v)=n 则G中存在哈密顿回路 必要条件： 定理15.6 无向图G是哈密顿图，则对于任意V1? V 且 V1 ≠ φ 均有 p(G-V1)≤ |V1| （p(G)为图G的连通分支数） 定理15.8 设u,v为n阶无向简单图G中两个不相邻的结点，且d(u)+d(v)=n则G为哈密顿图当且仅当 G∪(u,v)为哈密顿图 定理15.9 n（≥2)阶竞赛图G中都有哈密顿通路 定理7-3．1 连通无向图G的每一个结点都具有偶次数，当且仅当图G是个欧拉图。 证：首先假定图G是一个欧拉图。并且