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