第5章图论课件.pptVIP

定理2 任意无向连通图G至少存在一棵生成子树. 证: 1. 若G是无回路的，则G本身就是一棵生成子树； 2. 若G至少存在一个回路，在此回路中删去其中任意一条边得G1，此时不会影响图G的连通性；若G1仍然有回路，再在任意一个回路中删去其中任意一条边得G2，此时不会影响图G1的连通性。重复上述步骤，直至得到一个连通图T，且T是无回路的，但T与G有同样的结点集，所以，T是G的生成子树。 求生成子树的方法 破圈法　每次去掉回路中的一条边，其去掉的边的总数为m-n+1。 避圈法　每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。 例1 求下图(a)所示的图的生成子树。 定义 在权图G中，边权之和最小的生成树称为G的 最优树. 设连通权图G 有n个点m条边，则求最优树算法： 1) 将G的边按权从小到大排列，设为e1, e2,…, em ； 2) 取T={e1}, 再从e2开始依次将排好序的边加入T中，使加入后由T导出的子图(即由T的边作为边集合， T中边相关联的点作为点集所确定的子图)不含圈，直至T含有n-1条边. §5.4 偶图、匹配及其应用 定义1　若无向图G=V, E的结点集V能够划分为两 个子集V1, V2，满足V1∩V2＝?，且V1∪V2＝V，使得 G中任意一条边的两个端点，一个属于V1，另一个属 于V2，则称G为偶图。记为G=V1, V2, E . V1和V2称 为互补结点子集 在偶图G=V1, V2, E 中，若V1中的每个结点与V2 中的每个结点都有且仅有一条边相关联，则称偶图 G为完全偶图.记为Kn,m, 其中, n＝|V1|，m＝|V2|.　 上图a～d均是偶图，其中图b是完全偶图K2,3，图c 是完全偶图K3,3. 在图a中，G的互补结点子集为 V1={v1,v2,v3}，V2={v4,v5,v6,v7}； 在图d中，G的互补 结点子集为V1={v1,v2,v3}，V2={v4,v5,v6}。事实上，图c 和图d是同一个图，它们都是完全偶图K3,3. 定理1 无向图G=V, E为偶图的充分必要条件是G 的所有回路的长度均为偶数。 定义2　 给定图G=V, E，设M是E的一个不包含 环的子集，它的任意两条边在G均不相邻，则称M为 G匹配。 若匹配M的某条边与顶点v关联，则称v是M饱和 点，否则称v是M非饱和点 若G的每个顶点都是M饱和点，则称M为G完美匹 配，称含边数最多的匹配为最大匹配 设M为G的一个匹配，称G中由M中的边与非M中 的边交替组成的路为M交替路. 称起点与终点都为非饱和的为M交替路为M可扩 路. 定理1 (Berge,1957) G的匹配M为最大匹配当且仅当 G不包含M可扩路. 设S为图G的一个顶点子集，与S的顶点相邻的所 有顶点的集合，称为S的邻集. 记为N(S) 偶图存在匹配的条件：设偶图G=V1, V2, E , 1. 存在匹配的必要条件是|V1|≤|V2|. 2. G存在饱和V1的每个点的匹配,当且仅当对V1的任一子集有: |N(S)|≥| S| 3.如果满足条件 1) V1中每个结点至少关联t条边； 2) V2中每个结点至多关联t条边； 则G中存在从V1到 V2 的匹配,其中t为正整数(t条件) 4. 若G为每个点的度均为k(k0)的偶图,则G存在完美匹配 §5.5 特殊图 一 、 Euler图 哥尼斯堡七桥问题： 定义1　设G是无孤立结点的图，经过图中每边一次 且仅一次的通路(回路), 称为欧拉通路(回路)。具有 欧拉回路的图称为欧拉图。 　欧拉通路是经过图中所有边的通路中长度最短的通路（即为通过图中所有边的简单通路）； 　欧拉回路是经过图中所有边的回路中长度最短的回路（即为通过图中所有边的简单回路）。 例1 图a和图d是欧拉图；图b和图e不是欧拉图，但存在欧拉通路；图c和图f不存在欧拉通路。 §5.1 图的基本概念 一、 图的定义 例1 A、B、C、D四个班进行足球比赛，为了表示四个班之间比赛的情况，我们作出如右上图的图形。在该图中的4个小圆圈分别表示这四个班，称之为结点。如果两个班进行了比赛，则在两个结点之间用一条线连接起来，称之为边。这样，利用图形使得各班之间的比赛情况一目了然。 定义2一个图是一个序偶V, E，记为G＝V,E， 其中： 1) V＝{v1,v2,v3,…,vn}是一个有限的非空集合，vi(i＝1,2,3,…,n)称为结点,简称点,V为结点集； 2) E＝{e1, e2, e3,…, em}是一个有限的集合，ei (i＝1,2,3,…,m)称为边，E为边集， E中的每个元素都有V中的结点对与之对应。 1. 若边e与无序结点对(u,