图论中的边着色

边着色是将颜色分配给图的每条边，使得两个相邻边不分配相同的颜色。 如果有两条边，则可以称为相邻边，如果两条边通过相同的顶点连接。 在进行着色时，图的边必须分配最少数量的颜色。

我们没有任何 多项式 时间算法可用于使用最佳颜色数量对每张图进行边着色。 我们可以借助一个例子来理解它，如下所示

上图的边着色如下所示

上图包含 4 条边，其中两条边被涂成绿色，两条边被涂成黑色，因此总共需要 2 种颜色。 上述两种颜色分配如下，没有相邻的边被涂成相同的颜色。

如果图的每条边都以两个相邻边不包含相同颜色的方式着色，则这种类型的着色称为正确的边着色。 如果我们有一个 循环图，那么它必须包含边顶点对偶性，因此，类比变得等价。 在边着色的情况下，对图的所有边进行着色所需的最少颜色数称为最小边着色。

一些其他类型的边着色可用于各种问题，例如 Ramsey 定理和类似问题。 在这些类型的案例中，我们将使用 k 种颜色中的一种对图的所有边进行着色，并且数学家将研究生成的有色图子结构，以便他们可以找到存在的大小完全子图。

边着色也可以用于生成树的情况。 树的每条边都被着色，因此图不能包含相同颜色的循环。 在边着色的情况下，对给定图的所有边进行着色所需的最少颜色数可以称为树高。

一些重要术语

当我们学习边着色时，一些术语很有用。 这些术语描述如下

• 假设图表示为 G，颜色集合表示为 C。 正确的边着色可以描述为以将颜色从一条边分配给每条边的方式，如果两条边包含相同的顶点，则两条边必须分配不同的颜色。
• 正确的 k 边着色可以描述为具有 k 种颜色的正确边着色。 如果一个图中存在具有 k 种颜色的正确边着色，则该类型的图称为 k 边可着色。 我们可以借助一个例子来理解它，如下所示

上图包含 6 条边。 我们总共需要 3 种颜色来对图的所有边进行着色，这样两个相邻的边就不会包含相同的颜色。 在此图中，两条边被涂成红色，两条边被涂成绿色，两条边被涂成蓝色，因此总共需要 3 种颜色，并且相邻的边没有相同的颜色。 因此，该图是正确的 3 边可着色图或 3 边可着色图。

• 我们可以通过使用不同数量的颜色以不止一种方式对图进行着色，但是对正确的边着色进行着色所需的最少颜色数称为边的 色数 或 G 的色索引。 我们可以借助符号 χ` (G) 来表示边色数。

边着色示例

边着色包含许多示例，并且一些示例描述如下

示例 1

此图包含一个包含 14 条边的图，我们需要找到对该图进行着色的总颜色数。

解法：对于边着色，上图的所有边都必须以两个相邻的边没有相同颜色的方式着色。 在上图中，我们为所有边分配了一些颜色，这样相同的颜色就不应分配给两个相邻的边。 该图的边着色如下所示

在上图中，我们总共使用了 5 种颜色来对该图的所有边进行着色，这样 14 条边中没有两条相邻边被分配了相同的颜色。 因此，该图的最小边着色为 5。

χ`(G) = 5

示例 2

此图包含一个包含 9 条边的图，我们需要找到对该图进行着色的总颜色数。

解法：对于边着色，上图的所有边都必须以两个相邻的边没有相同颜色的方式着色。 在上图中，我们为所有边分配了一些颜色，这样相同的颜色就不应分配给两个相邻的边。 该图的边着色如下所示

在上图中，我们总共使用了 4 种颜色来对该图的所有边进行着色，这样 9 条边中没有两条相邻边被分配了相同的颜色。 因此，该图的最小边着色为 4。

χ`(G) = 4

示例 3

此图包含一个包含 15 条边的图，我们需要找到对该图进行着色的总颜色数。

解法：对于边着色，上图的所有边都必须以两个相邻的边没有相同颜色的方式着色。 在上图中，我们为所有边分配了一些颜色，这样相同的颜色就不应分配给两个相邻的边。 该图的边着色如下所示

在上图中，我们总共使用了 4 种颜色来对该图的所有边进行着色，这样 15 条边中没有两条相邻边被分配了相同的颜色。 因此，该图的最小边着色为 4。

χ`(G) = 4

示例 4

此图包含一个包含 18 条边的图，我们需要找到对该图进行着色的总颜色数。

解法：对于边着色，上图的所有边都必须以两个相邻的边没有相同颜色的方式着色。 在上图中，我们为所有边分配了一些颜色，这样相同的颜色就不应分配给两个相邻的边。 该图的边着色如下所示

在上图中，我们总共使用了 4 种颜色来对该图的所有边进行着色，这样 18 条边中没有两条相邻边被分配了相同的颜色。 因此，该图的最小边着色为 4。

χ`(G) = 4

示例 5

此图包含一个包含 8 条边的图，我们需要找到对该图进行着色的总颜色数。

解法：对于边着色，上图的所有边都必须以两个相邻的边没有相同颜色的方式着色。 在上图中，我们为所有边分配了一些颜色，这样相同的颜色就不应分配给两个相邻的边。 该图的边着色如下所示

在此图中，我们总共使用了 4 种颜色来对该图的所有边进行着色，但是三个相邻的边被涂上了相同的颜色黑色（由 c 表示），这违反了边着色的规则。 因此，上图不是正确的边着色。

但是，可以使用最少数量的颜色为此图创建正确的边着色。 该图的正确边着色如下所示

在上图中，我们总共使用了 4 种颜色来对该图的所有边进行着色，这样 8 条边中没有两条相邻边被分配了相同的颜色。 因此，该图的最小边着色为 4。

χ`(G) = 4