首页 > 正在进行安全检测...

正在进行安全检测...

发布时间：1714294905 来源：文档文库

小中大

字号：

手机查看

云南大学数学与统计学院
实验报告
课程名称：算法图论实验指导教师：李建平实验编号：
05 学院：数学与统计学院

一、实验目的

掌握二部图边染色数问题和二部图最大匹配问题的求解算法，给出二部图的边染色方案 VS2010（C++）
给定一个二部图GV,E，求边染色数'G，并给出染色方案。 A.二部图边染色问题求解思想
1）对于给定的二部图G，利用二部图最大匹配算法求得G的一个最大匹配M1，对G1=G-M1再利用二部图匹配算法求得G1的一个最大匹配M2,..., 这样可以得到图G的边子集被划分成G个集合M1,M2,...,M，从而可对G进行G染色。根据定理6.1，设二、实验环境三、实验内容四、实验过程
学期：2013~2014学年上学期姓名：卢富毓实验日期：2013-12-13 专业：信息与计算科学
成绩：
学号： 20101910072 实验学时： 2学时完成日期：2013-12-14 年级： 2010级

实验名称：二部图的染色问题实验要求：必做
GS,T;E是一个二部图，则'GG，其中G为G的最大的度。
设图G=(S,T;E为二部图，可用反圈法求二部图的匹配 ① 选初值：取X0 uS|u是关于M的未盖点② 在Xk中选边uiuj原则，这里uiXk,ujVXk：若uiXkS，则只能选以ui为端点的非M边若uiXkT，则只能选以ui为端点的M边 ③ 若在某步出现下列情形之一停止
2 二部图最大匹配算法
 情形1：Xk中有T型未盖点，即已找到增广路P，进行增广匹配，构造新的匹配 M'ME(PMEPEPM
情形2：上述情形1不存在，而Xk中无边可选，说明G不存在关于M的增广路，进而M为最大匹配。 B.实现过程
对任意给定的一个图，首先判断它是否为二部图，若是二部图，则给出二部图的边染色方案，若不是二部图，程序结束。二部图的S集和T集的划分，这里采用如下定义：
SuV|du,v是偶数，TuV|du,v是奇数，计算两点之间的最短距离用到的是第 1 页共 9 页

Dijkstra算法（令各边权值为1），注意到二部图可能是不连通图，在代码实现过程中也加入了相关设计，保证程序的健壮性，运行结果中给出一个测试实例。运行结果：

五、实验总结
求二部图的边染色数方案是基于二部图的最大匹配算法的实现，了解了设计思路之后解决的时候可能是非常简单的。但是对一般图来说，求二部图的边染色数是NP-完备问题，如何解决还需要查阅相关资料。
第 2 页

《正在进行安全检测....doc》

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档

文档为doc格式

相

关

案

例

正在进行安全检测...

相关推荐

推荐内容