图论中的二分图

当我们学习二分图的概念时，我们需要了解图。图是由顶点集和边集组成的。这些边用于连接顶点。因此，图论可以被描述为对图的研究。

二分图

在各种类型的图中，有一种特殊的图称为二分图。二分图包含一些特性，如下所述

• 在二分图中，必须有两个顶点集，X 和 Y。
• 顶点的连接只能在两个不同的顶点集之间进行。这意味着 X 中的顶点只能与 Y 中的顶点连接。
• 不能在同一集合的顶点之间进行连接。这意味着 X 中的顶点不能连接到同一集合 X 中的顶点。对于集合 Y，情况也是如此。

还有一种定义二分图的方法，如下所述

• 假设有一个图 G = (V, E)。如果该图的顶点集 V 被划分为两个子集 X 和 Y，并且该图的边集 E 中的所有边都必须包含两个端点顶点。第一个端点顶点属于集合 X，第二个端点顶点属于集合 Y。这种顶点划分也称为双划分。

例如：在此示例中，我们有一个图，并检查它是否是二分图。

解答：在上图中，我们有两个顶点集，第一个集合有 3 个顶点（a、b、c），第二个集合包含 4 个顶点（w、x、y、z）。在此图中，第一个集合的顶点仅与第二个集合的顶点连接，反之亦然。同一集合中的任何两个顶点之间都没有连接。因此，该图是二分图。

如何识别二分图

借助以下算法，我们可以检查给定图是否是二分图。

1. 首先，我们从给定的图中选择任何一个顶点，并将其分配给两个集合中的一个，例如 X。
2. 之后，我们将它所有的邻居顶点分配到另一个集合，即 Y。
3. 现在，我们考虑集合 Y 中的每个顶点，并将集合 Y 的所有邻居顶点分配到集合 X。类似地，我们考虑集合 X 中的每个顶点，并将集合 X 的所有邻居顶点分配到集合 Y。
4. 现在，我们重复步骤 3，直到我们将所有顶点都分配到一个集合。
5. 最后，我们检查所有顶点，找出是否有任何相邻顶点位于同一集合中。如果能找到，则该图不是二分图。否则，该图是二分图。

例如

二分图有很多例子，如下所示

示例 1

在此示例中，我们有一个具有两个集合 V1 和 V2 的图。在这里，我们检查它是否是二分图。

解答：在上图中，我们可以看到以下内容

上图有两个顶点集。集合 V1 的顶点是 {a, b}，集合 V2 的顶点是 {c, d, e}。集合 V1 的顶点与集合 V2 的顶点连接。它们没有在同一集合内连接。因此，该图是二分图。

示例 2

在此示例中，有一个图，我们检查它是否是二分图。

解答：这里，我们将上面的图视为一个随机图 G1(V, E)。我们尝试满足二分图的条件。为此，必须将顶点集划分为两个集合，使得图中的每条边连接两个顶点集。现在，我们将 G1 的顶点集划分为以下方式

该图与上面显示的图 G1 相同，但两图的表示不同。在此图中，我们将顶点集 V 划分为两个不相交的顶点集 V1 和 V2，其中 V = {A, B, C, D, E}，分为两个集合 V1 = {A, D} 和 V2 = {B, C, E}。我们可以通过观察图的顶点或边来证明该图是二分图。

• 上述集合的顶点，即 A、B、C、D 和 E，满足二分图的定义。在此图中，集合 V1 的顶点仅连接到集合 V2 的其他顶点。类似地，集合 V2 的顶点仅连接到集合 V1 的顶点。该图不包含任何连接同一集合 V1 或 V2 的顶点的顶点。
• 上述图中边集 E = {E1, E2, E3, E4, E5, E6} 的边也满足二分图的定义。在上图中，我们可以看到每条边都有两个端点，一个端点在集合 V1 中，另一个端点在集合 V2 中。该图不包含任何端点位于同一顶点集 V1 或 V2 中的边。

因此，上述图是二分图。

二分图的性质

二分图有各种性质，其中一些如下所示

1. 二分图不包含奇数环

假设有一个图 G1，其中包含一个随机环 ABDCA。另一个环是 DEACD。

我们可以通过计算图中不同顶点的数量来计算环的长度。在上面的两个环中，都有 4 个顶点。因此，这两个环都是偶环。

2. 如果一个图是二分图，那么它总是 2 可着色的，反之亦然

在图着色问题中，如果一个图是 2 可着色的，那么它意味着我们需要 2 种不同的颜色来给图的所有顶点着色，以便图中相邻的两个顶点不应具有相同的颜色。

如果我们有一个二分图，那么它包含两个顶点集和一些边。该图的每条边都在两个顶点集中的一个中有一个端点。因此，我们可以使用 2 种不同的颜色来给该图的所有顶点着色，并且该图中没有两个相邻的顶点具有相同的颜色。

3. 二分图的子图也是二分图

为此，我们假设图 G1 包含一个随机子图 G_S(V_S, E_S)。其中 V_S 是顶点集，即 V_S = {A, B, C, D, E}，E_S 是边集，即 E_S = {E₁, E₂, E₃, E₄, E₅}。因此，子图 G_S 也包含二分图 G1。

4. 如果图是无向二分图，则每个顶点划分集的度必须相等。

从上面的示例 2 中，图 G1 被划分为两个顶点集 V1 和 V2，其中 V1 = {A, D} 和 V2 = {B, C, E}。现在，集合 V1 的度可以通过将顶点 A 和 D 的度相加来计算。在上面的示例中，我们可以看到顶点 A 和顶点 D 的度为 3。因此，集合 V1 的度为 6。

类似地，集合 V2 的度可以通过将顶点 B、C 和 E 的度相加来计算。在上面的示例中，我们可以看到顶点 B、顶点 C 和顶点 E 的度为 2。因此，集合 V2 的度为 6。所以，顶点集 V1 和 V2 的度是相同的，即 6。因此，证明了在无向二分图中，两个顶点划分集的度数是相等的。

5. 假设有一个二分图，被划分为两个集合 X 和 Y。如果 |X| ≠ |Y|，则该图不包含完美匹配。

二分图的应用

二分图在许多领域都有应用，其中一些如下所示

匹配问题

与匹配相关的问题可以通过二分图建模。例如，需要二分图将求职者与职位空缺匹配，或者在为学生分配项目导师时。借助二分图，可以自然地将一个集合的顶点与另一个集合的顶点匹配。

社交网络

二分图可用于显示社交网络问题。例如，假设有两个顶点集，第一个集合的顶点用于显示用户，另一个集合的顶点用于显示社区、兴趣或群组等项目。这些顶点可以模拟社交网络。借助二分图，可以很容易地分析用户与其兴趣之间的联系。

网络搜索引擎

借助二分图，可以轻松定义搜索引擎的查询和点击数据。第一个集合的顶点用于显示查询，另一个集合的顶点用于显示网页。

完全二分图

有多种方法可以定义完全二分图，如下所述

• 一个集合中的每个顶点都必须与另一个集合中的每个顶点连接。这意味着 X 中的所有顶点只能与 Y 中的所有顶点连接。
• 如果给定的图既是完全图又是二分图，则该图称为完全二分图。
• 完全二分图用符号 K_{x, y} 表示，其中 x 用于表示第一个集合中的顶点数，y 用于表示第二个集合中的顶点数。

完全二分图的例子

我们有很多完全二分图的例子，如下所示

示例 1

在此示例中，我们有一个图 G，并检查它是否是完全二分图。

解答：在此图中，我们有两个顶点集 X 和 Y，其中左侧部分是集合 X，右侧部分是集合 Y。这里，集合 X 有一个顶点，集合 Y 有四个顶点。X 的顶点连接到 Y 集中的每个顶点，并且没有顶点连接到同一集合。因此，该图是完全二分图。该图也称为 K_{1, 4}（因为集合 X 有一个顶点，集合 Y 有 4 个顶点）。

示例 2

在此示例中，我们有一个具有两个集合 X 和 Y 的图。

解答：在此图中，集合 X 的所有顶点与集合 Y 的所有顶点之间都有连接。没有顶点连接到同一集合。该图也称为二分图，也是一个完全图。因此，该图是完全二分图。在此图中，我们有 3 个顶点在集合 X 中，2 个顶点在集合 Y 中。所以它被称为 K_{3, 2}。

示例 3

在此示例中，我们有一个图 G，并检查它是否是完全二分图。

解答：在此图中，我们有两个顶点集 X 和 Y，其中集合 X 包含四个顶点（V1、V2、V3 和 V4），集合 Y 包含两个顶点（W1 和 W2）。集合 X 的所有顶点都连接到集合 Y 的每个顶点，并且没有顶点连接到同一集合的顶点。因此，该图是完全二分图。该图也称为 K_{4, 2}（因为集合 X 有 4 个顶点，集合 Y 有 2 个顶点）。

二分图的色数

在对二分图进行着色时，有一些要点很重要，这些要点如下所述

• 我们可以用最少的 2 种颜色来给任何二分图着色。
• 在给图着色时，我们必须检查一个属性，即图中每条边的端点不应以相同的颜色着色。
• 因此，二分图也称为 2 可着色。

注意：如果一个二分图不包含任何边，则该图是 1 可着色的。

例如：在此图中，我们有一个二分图，它有两个顶点集。

在此图中，没有边连接集合 X 的顶点和集合 Y 的顶点。当我们给这张图着色时，我们只需要 1 种颜色，如下所述

这里，色数为 1，因为给上面的图着色只需要 1 种颜色。

色数示例

示例 1

在此示例中，我们有一个二分图，需要计算该图的色数。

在上图中，只需要两种颜色来给上图着色。因此，色数 = 2。

示例 2

在此示例中，我们有一个二分图，它有两个顶点集，需要计算该图的色数。

在上图中，只需要两种颜色来给上图着色。因此，色数 = 2。

示例 3

在此示例中，我们有一个二分图，它有两个顶点集，需要计算该图的色数。

该图可以用最少的两种颜色着色。因此，色数 = 2。

二分图中的完美匹配

我们可以使用下面显示的公式来确定二分图中的完美匹配

K_n,n 的完全匹配数 = n!

完美匹配的性质

现在，我们来理解完美匹配在二分图中的一些性质。为此，我们假设一个二分图 G，它被划分为两个集合 X 和 Y。完美匹配的性质如下所示

• 如果二分图的集合不相等，即 |X| ≠ |Y|，在这种情况下，该图不包含完美匹配。
• 如果我们考虑 X 的所有子集，并且子集中的元素数量 ≤ 邻域子集中的元素数量，在这种情况下，二分图 G 包含完美匹配。

最大边数

如果在二分图中 n 个顶点，那么该图中的边数最多为 (1/4)*n²。换句话说，如果一个二分图有 n 个顶点，那么最大可能的边数是 (1/4)*n²。

说明

• 假设我们有一个二分图，它被双划分为两个集合 V1 和 V2，其中 |V1| = k 且 |V2| = |n-k|。
• 在此图中，这两个集合之间的边数最多为 k(n-k)，当 k = n/2 时可最大化。因此，图中存在边的最大数量是 ¼ n²。
• 如果一个图 G 包含多于 ¼ n² 条边和 n 个顶点，在这种情况下，图 G 包含一个三角形。
• 二分图中没有奇数环。因此，上述性质（G 包含三角形）在二分图中不可能存在。

二分图示例

二分图有很多例子，如下所示

示例 1

在此示例中，我们有一个图，它包含两个顶点集。现在，我们检查它是否是二分图。

解答：在此图中，我们有两个顶点集，第一个集合包含 4 个顶点，第二个集合包含 3 个顶点。第一个集合的顶点仅连接第二个集合的顶点。类似地，第二个集合的顶点仅连接第一个集合的顶点。同一集合中的任何两个顶点之间都没有连接。因此，它满足二分图的所有条件。因此，该图是二分图。

示例 2

在此示例中，有一个具有 10 个顶点的二分图。利用这些顶点，我们计算最大可能的边数。

解答：如果有 n 个顶点，我们可以使用以下公式来计算最大可能的边数

1/4 * n²

从上面的问题中，我们有 n = 10。所以，我们将它代入这个公式，如下所示

= 1/4 * (10)²

= 1/4 * 100

= 25

因此，最大边数为 25。

示例 3：在此示例中，我们有一个图，它包含两个顶点集。现在，我们检查它是否是二分图。

解答：在此图中，我们有两个顶点集 X 和 Y，其中集合 X 包含 2 个顶点，集合 Y 也包含 2 个顶点。集合 Y 的顶点仅连接到集合 X 的顶点。但是集合 X 的一些顶点连接到同一集合，即 X，而一些顶点连接到另一个集合 Y。这意味着两个同集顶点之间存在连接。因此，这些性质不满足二分图的所有条件。因此，该图不是二分图。