离散数学ch14v051601.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 实例 *  强连通 单连通 弱连通 有向图中的短程线与距离 u到v的短程线: u到v长度最短的通路 (设u可达v) 距离du,v: u到v的短程线的长度 若u不可达v, 规定du,v=∞. 性质： du,v?0, 且du,v=0 ? u=v du,v+dv,w ?du,w 注意: 没有对称性 * * 扩大路径法 无向图中 设G=V,E为 n 阶无向图，E??. 设 ?l 为G中一条路径，若 此路径的始点或终点与通路外的顶点相邻，就将它们扩到通 路中来，继续这一过程，直到最后得到的通路的两个端点不 与通路外的顶点相邻为止. 设最后得到的路径为?l+k（长度 为 l 的路径扩大成了长度为 l+k 的路径），称?l+k为“极大路 径”，称使用此种方法证明问题的方法为“扩大路径法”. 有向图中类似讨论，只需注意，在每步扩大中保证有向边方 向的一致性. * 实例 由某条路径扩大出的极大路径不惟一，极大路径不一定是 图中最长的路径 上图中，(1)中实线边所示的长为2的初始路径?，(2),(3),(4) 中实线边所示的都是它扩展成的极大路径. 还能找到另外的极大路径吗？ (1) (2) (4) (3) * 扩大路径法的应用 例4 设 G 为 n（n?3）阶无向简单图，? ? 2，证明G 中存在 长度 ? ?+1 的圈. 证 设 ? = v0v1…vl 是由初始路径 ?0 用扩大路径法的得到的极 大路径，则 l ? ? （为什么？）. 因为v0 不与 ? 外顶点相邻，又 d(v0) ? ?，因而在 ?上除 v1 外，至少还存在 ??1个顶点与 v0 相邻. 设 vx 是离 v0 最远的顶 点，于是 v0v1…vxv0 为 G 中长度 ? ?+1 的圈. * 二部图 定义14.23 设 G=V,E为一个无向图，若能将 V分成 V1和V2 (V1?V2=V，V1?V2=?)，使得 G 中的每条边的两个端点都是 一个属于V1，另一个属于V2，则称 G 为二部图 ( 或称二分 图、偶图等 )，称V1和V2为互补顶点子集，常将二部图G 记为V1,V2,E. 又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相 邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|. 注意，n 阶零图为二部图. * 由定理14.10可知图9中各图都是二部图， 哪些是完全二部图？哪些图是同构的？ (a)(b)(c)为K6的子图; c为完全二部图K3,3, (e). d为K5的子图，为完全二部图K2,3, (f). 1 2 4 6 3 5 1 2 4 3 5 6 a b c d e f 1 2 4 6 3 5 1 2 4 3 5 1 2 3 5 4 6 2 4 1 3 5 * 二部图的判别法 定理14.10 无向图G=V,E是二部图当且仅当G中无奇圈 由定理14.10可知图9中各图都是二部图，哪些是完全二部 图？哪些图是同构的？ 无向图的关联矩阵 设无向图G=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}. 令mij为vi与ej的关联次数, 称(mij)n?m为G的关联矩阵, 记为 M(G). mij的可能取值为:0,1,2 * 例如 e1 e2 e3 e4 e5 e6 v5 v1 v2 v3 v4 M(G)= 2 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 v1 v2 v3 v4 v5 e1 e3 e5 * 14.4 图的矩阵表示 无向图的关联矩阵（对图无限制） 定义14.24 无向图G=V,E，|V|=n，|E|=m，令 mij为 vi 与 ej 的关联次数，称(mij)n?m为G 的关联矩阵，记为M(G). 性质 无环有向图的关联矩阵 * 则称(mij)n?m为D的关联矩阵, 记为M(D). 设无环有向图D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}. 令 (3) ej与ek是平行边 ? 第j列与第k列相同 (2) 第i行1的个数等于d+(v), 第i行-1的个数等于d-(v) 性质: (1) 每列恰好有一个1和一个-1 实例 * v1 v2 v3 v4 e2 e1 e3 e4 e5 e6 e7 M(D)= -1 1 0 0 0 –1 1 0 -1