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