C图进阶篇：如何深入理解二分图染色与匈牙利算法？

本文共计3814个文字，预计阅读时间需要16分钟。

1. 前言 + 图表 + 再称图 + 二部分图或称图为偶图，是图论中的一种特殊类型，具有广泛的应用场景。什么是二分图？二分图一般是指无向图。

看待问题需有哲学思考，有二分图也可是有向图。

1. 前言

二分图又称作二部图或称为偶图，是图论中的一种特殊类型，有广泛的应用场景。

什么是二分图？

• 二分图一般指无向图。看待问题要有哲学思想，有二分图也可以是有向图。

• 如果图中所有顶点集合能分成两个独立的子集，且任一子集中的任意顶点之间没有边连接，则称这样的图为二分图。

如下图中的图结构都可称为二分图。

二分图的特点：

• 理论而言，图中至少有一个环，如果图中无环，则图退化成树。在研究树和图时，一般会把树问题当成图问题的子类。
• 二分图中不能有奇数个顶点组成的环。

如何验证二分图中的环不能是奇数个顶点？

• 环也称为回路，指路径的起点和终点为同一顶点。
• 证明这个问题，可以使用染色算法，此算法是判断二分图的经典算法。

2. 染色算法

二分图的定义已经说明，图中存在二个独立的子集，为了区分这两个子集，可以给其中一个子集中的顶点染上红色，另一个子集中的顶点染上蓝色。具体是什么颜色并不重要，只要能区分就可以。