离散数学中的二分图

如果我们想学习二分图，我们必须了解图。图可以被描述为一组顶点，这些顶点通过一组边相互连接。在本节中，我们将学习二分图的定义、完全二分图、二分图的色数、它的性质和例子。

二分图的定义

二分图可以被描述为一种特殊的图，它具有以下性质

• 该图总是有两个集合 X 和 Y，包含顶点。
• 在该图中，集合 X 中的顶点只能与集合 Y 连接。
• 我们不能连接同一集合内的顶点。

二分图的例子如下所示

在上图中，我们有以下内容

• 我们可以将给定图的顶点分解为两个集合。
• 分解后的集合是 X = {A, C}，Y = {B, D}。
• 集合 X 中的顶点只能与集合 Y 连接，反之亦然。
• 我们不能连接同一集合的顶点。
• 因此，给定的图是二分图。

完全二分图

• 我们可以用多种方式定义二分图。换句话说，我们可以说完全二分图有许多定义，如下所述
• 如果集合 X 中的每个顶点都与集合 Y 中的每个顶点连接，则该图被称为完全二分图。
• 如果一个图既是二分图又是完全图，则称其为完全二分图。
• 如果存在一个完全的二分图，那么该图将被称为完全二分图。

完全二分图的例子

完全二分图的例子如下所示

在上图中，我们有以下内容

• 上图是二分图，也是完全图。
• 因此，我们可以称上图为完全二分图。
• 我们也可以称上图为 **k_{4, 3}**。

二分图的色数

当我们想对任何二分图进行正确着色时，我们必须遵循以下性质

• 为此，我们需要最少的两种颜色。
• 我们必须使用不同的颜色为每条边的端点着色。
• 在这种情况下，二分图将是2可着色的。

注意：如果二分图中没有边，那么该图将是1可着色的。

二分图色数的例子

在上图的二分图中，色数是2，因为左侧的顶点用橙色着色，右侧的顶点用红色着色。所以有两种颜色。因此，色数 = 2。

二分图的性质

二分图有各种性质，其中一些重要的性质如下所述

• 二分图是2可着色的。
• 二分图中没有奇数环。
• 如果二分图中存在任何子图，那么该子图也将是二分图。
• 如果存在 |X| ≠ |Y| 的情况，那么二分图将不包含以 X 和 Y 为二分划分的完美匹配。
• 如果一个二分图包含一个以 X 和 Y 为二分划分，那么它将具有以下关系

二分图的完美匹配

在二分图中，完美匹配的公式如下所述

为了理解这一点，我们将假设我们有一个二分图 G 及其二分划分 X 和 Y。现在我们将展示完美匹配的案例

• 如果存在 |X| ≠ |Y| 的情况，那么二分图将不具有完美匹配。
• 如果存在一个子集邻域元素的数量大于或等于 X 的所有子集及其数量的情况，在这种情况下，二分图将包含以 X 和 Y 为二分划分的完美匹配。

最大边数

• 如果一个二分图有 n 个顶点，那么该图最多包含 (1/4)*n² 条边。
• 在二分图中，'n' 个顶点的最大可能边数为 (1/4)*n²。

说明

• 假设 V1 和 V2 是图的二分划分，其中 |V1| = k 且 |V2| = n - k。
• k(n-k) 是 V1 和 V2 之间最大边数，当 k = n/2 时，边数最大化。
• 因此，最多可以存在 1/4 * n² 条边。
• 如果一个图 G 包含 n 个顶点并且边数超过 1/4 * n²，那么该图 G 将包含一个三角形。
• 二分图不包含奇数环。这就是为什么它不包含在这样的图中。

二分图的例子

二分图有各种例子，其中一些如下所述

示例 1：在本例中，我们需要证明给定的图是否为二分图。

解决方案

我们可以用另一种方式绘制上述图，如下所示

在上图中，我们有以下内容

• 在上图中，我们有两个顶点集，即 X 和 Y。
• 集合 X = {1, 4, 6, 7}，集合 Y = {2, 3, 5, 8}。
• 在该图中，集合 X 的顶点仅与集合 Y 的顶点连接，集合 Y 和集合 X 也一样。
• 我们不能连接同一集合的顶点。
• 所有这些性质都满足二分图的定义。

因此，上图被称为二分图。

示例 2：在本例中，我们有 12 个二分图的顶点，我们需要确定该图的最大边数。

解决方案：正如我们上面学到的，任何具有 n 个顶点的二分图的最大边数 = (1/4) * n²

现在我们将 n = 12 代入上述公式并得到以下结果

在二分图中，12 个顶点的最大边数 = (1/4) * (12)²

= (1/4) * 12 * 12

= 1/4 * 144

= 36

因此，在二分图中，12 个顶点的最大边数 = 36。