设G=(VE)是一个无向图,如果顶点V可分割为两个互不相交的子集(AB),并且图中的每条边所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为一个二分图.
给定一个图,可以使用染色法来判断这个图是否是一个二分图.
可用于处理最大匹配的问题.常用的算法是:匈牙利算法.
如果两个格子之间能相互攻击,则在这两个格子之间建立一条边; 原题就等价于 选最多的点使得两两之间没有边.
能使用匈牙利算法来解决的前提条件是:这个图是一个二分图. 证明此题中的骑士摆放是一个二分图:
给棋盘染色 横纵坐标和为偶数的染成黑色 横纵坐标和奇数染成白色. 此时可以发现当棋子位于黑色格子时可以跳的格子都是白色的.因此所有的边都在两个集合之间.
假设当前格子的坐标为(x y),则当跳了一步之后,nx + ny 的奇偶性与 x + y 的奇偶性是相反的.因为在跳的过程中坐标值的变换是一个奇数 因此一个数加减一个奇数,它的奇偶性一定会发生变换.因此是一个二分图.