二部图的定义与判断

二部图（bipartite graph）是一种特殊的无向图，其节点可以分为两个不相交的子集，且子集内的节点间没有边相连。在实际应用中，二部图被广泛用于描述两类对象之间的关系，如顾客和商品、读者和书籍等等。

定义

在一个二部图中，若将节点分为X和Y两个集合，则对于任意一条边(x, y)，节点x属于集合X，节点y属于集合Y。同时，对于节点集合X中的任意两个节点，它们之间没有边相连；节点集合Y中的节点也满足这个条件。因此，二部图中不存在环。

判断

对于给定的一个图，如何判断它是不是一个二部图呢？常用的方法是通过染色法进行判断。具体步骤如下：

1.任选一个节点，将其染成红色（也可以染成蓝色）。

2.将与该节点相邻的所有节点染成蓝色（若已经染色，则不必重复染色）。

3.将与这些蓝色节点相邻的所有节点染成红色（若已经染色，则不必重复染色）。

4.重复步骤2和3，直到所有节点都被染色或发现相邻节点已经被染成相同颜色。

5.若整个过程中没有出现相邻节点被染成相同颜色的情况，则该图是一个二部图；否则，它不是一个二部图。

应用

二部图在实际应用中有广泛的用途。例如，在推荐系统中，我们可以将用户和物品分别当成两个节点集合，若用户浏览了某个物品，则在两个节点之间连一条边，这样我们就可以基于这个二部图来给用户推荐物品。在匹配问题中，若有两个集合A和B，我们需要从A中选出若干元素和B中相应的若干元素进行匹配，使得匹配成功的元素尽量多。这个问题可以利用二部图得到解决。在电子商务中，我们可以将商家和商品分别当成两个节点集合，若某个商家销售过某个商品，则在两个节点之间连一条边，这样就可以找到热门商品和热门商家。