计算机七章重点分析.ppt

二部图 若能将无向图G=V,E的顶点集V划分成两个子集V1和V2(V1∩V2=?),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称为偶图).V1,V2称为互补顶点子集,此时可将G记成G= V1,V2,E。 若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图，若?V1? =n, ?V2?=m,则记完全二部图G为Kn,m 判断二部图的定理 一个无向图G=V,E是二部图当且仅当G中无奇数长度的回路. 设G=V,E为无向图，G中有边集M?E，若M中任意两条边均不相邻，则称M为G中的匹配(或边独立集)。 若在M中再加入任何1条边就都不是匹配了,则称M为极大匹配. 边数最多的匹配称为最大匹配,最大匹配中的元素(边)的个数称为G的匹配数。 完备匹配 设G=V1,V2,E为一个二部图,M为G中一个最大匹配,若?M? =min{?V1?,?V2?},则称M 为G中的一个完备匹配. 此时若?V1? ≤?V2?,则称M为V1到V2的一个完备匹配.如果?V1?= ?V2?,这时M为G中的完美匹配. 图7.4 例 某中学有3个课外小组:物理组、化学组、生物组.今有张、王、李、赵、陈5名同学.若已知: (1)张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员; (2)张为物理组成员,王、李、赵为化学组成员,王、李、赵、陈为生物组成员; (3)张为物理组和化学组成员,王、李、赵、陈为生物组成员. 问在以上3种情况下能否各选出3名不兼职的组长？ 解: 设v1,v2,v3,v4,v5分别表示张、王、李、赵、陈.u1,u2,u3分别表示物理组、化学组、生物组.在3种情况下作二部图分别记为G1,G2,G3,如图所示. 对于哥尼斯堡七桥问题，大数学家欧拉最先意识到哥尼斯堡七桥问题的求解与 A, B, C, D 的大小和它们之间的长度无关，从而将问题求解转换为对多重图的遍历，即：找到一条遍历多重图每条边恰好一次的回路。若需要，回路可以重复访问结点。 欧拉图 定义 给定无向连通图 G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉通路；若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路。 具有欧拉回路的图称为欧拉图。 存在欧拉通路的图,称为半欧拉图。 图中（1）（2）(3) 不是欧拉图, (4) 是欧拉图. 例 是欧拉图； 不是欧拉图，但存在欧拉通路，是半欧拉图； 即不是欧拉图，也不存在欧拉通路。 例(蚂蚁比赛问题) 甲、乙两只蚂蚁分别位于如下图G中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？ 例 图a)存在一条欧拉通路：v3v1v2v3v4v1； 图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图； 图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。 【例 】设某城市的街道布局如下图所示。每条边代表一条特定街道的一段街区，每个结点代表街区间的交点。扫雪车车库位于结点 d。证明存在一条路线使得扫雪车清扫每个街区恰好一次且清扫完最后一个街区正好返回车库。为这个扫雪车找出完成任务的路线。 解：首先，注意到图是连通的，并且每个结点的度数为偶数，那么，根据定理可以推知出图中存在欧拉回路。而图是扫雪街区布局的模型图， 所以可以推出存在一条使得扫雪车经过每个街区恰好一次最后回到车库的路线。 哈密尔顿图 智力游戏 爱尔兰数学家哈密顿给友人的信中提到一个智力游戏：用一个正12面体表示地球，正12面体的20个顶点表示20个城市(图a)，要求从任一城市出发，沿12面体的边走过每个城市且仅一次，最后回到出发点。 归结为求通过图（b）中各个顶点一次且仅一次的回路。 哈密尔顿图 哈密尔顿通路(回路)、哈密尔顿图 经过图中每个顶点一次且仅一次的通路(回路)称为哈密尔顿通路(回路).存在哈密尔顿回路的图称为哈密尔顿图.存在哈密尔顿通路的图称为半哈密尔顿图. 哈密尔顿图的充分条件和必要条件 定理 （必要条件） 设图G是哈密顿图，如果从图G中删去p个点后得到图G’，则图G’的连通分支数小于等于p。 推论 当图中含有割点或割边时，此图必不是哈密顿图。 定理 (充分条件) 设G是具有n个顶点的无向简单图，如果图中任意两个不同的顶点的度数之和大于等于n，则G中存在哈密尔顿回路，即图G是哈密顿图。 例 在图中，任意两个结点的度数之和为4，结点数为6，即有4?6，，但它仍然是哈密尔顿图。 例 一个班的学生共计选修a, b, c, d, e, f 六门课程，其中一部分人同时选修a, c, d , 一部分人