精品文档---下载后可任意编辑二部图的非正常边染色的开题报告一、问题阐述:二部图是由两个不相交的集合构成,若图中每条边的两个端点分别属于这两个集合中的一个,则该图称为二部图。非正常边染色问题是指给定一个二部图,以及其中一些不合法的边(即连接同一集合内的两个点的边),如何在保证每个点的相邻边颜色不同的前提下,尽可能多地将所有合法边染成黑色或白色,使得染色后的黑白边数差最小。二、问题分析:1.二部图判定算法:在分析二部图的非正常边染色问题前,我们需要先了解如何判定一个图是否为二部图。二部图的判定算法主要步骤如下:- 对图进行遍历,找到一个未被染色的点;- 将该点染成黑色;- 对该点的所有邻居节点进行标记:标记黑色节点的邻居为白色,标记白色节点的邻居为黑色;- 递归遍历所有未被染色的节点,直至所有节点被染色或找到某个节点与其邻居节点颜色相同,说明该图不是二部图。根据上述算法,我们可以在 O(n+m)的时间复杂度内判定一个图是否为二部图。2.非正常边染色问题:一般而言,非正常边染色问题可以通过图的最大匹配算法来求解。最大匹配算法主要步骤如下:- 建立一个空的匹配集合 M;- 在图中寻找一个增广路径 P,即从一个未匹配点开始,交替经过未被匹配的边和已经被匹配的边,直至到达另一个未匹配的点;- 将 P 中未匹配边和已匹配边交换状态,即原来不在 M 中的边加入M,原来在 M 中的边从 M 中删除;- 重复步骤 2-3,直至不存在增广路径。精品文档---下载后可任意编辑由于所有的非正常边连接的是同一集合中的点,因此我们可以将每个同一集合中的点看做一个点,将每个非正常边看做一个虚点,并将每条非正常边所连接的点与虚点相连,构成增广图。通过增广图的最大匹配问题即可求解原问题。三、实验方案:1.二部图判定算法:根据上述算法,实现一个二部图判定算法。具体实现时,采纳深度优先遍历算法对图进行遍历,在每次对未染色节点进行染色时,对其邻居节点进行标记。2.非正常边染色问题:根据上述算法,实现一个增广图的最大匹配算法,并将非正常边加入增广图。在求解过程中,记录黑白边数的差值,使其最小。四、预期结果:通过本实验,估计能够实现一个可以判定二部图并解决非正常边染色问题的程序。该程序可以模拟现实中有一些不满足规定的情况下,尽可能多地将合法边染成黑色或白色,避开出现矛盾。最终的结果应该能够满足染色合法性要求,并保证黑白边数的差值最小。