图论中的色多项式

在一个图中，色多项式可以被描述为一个多项式函数，它用于表示给定的颜色对图进行着色的可能性次数。使用符号 f(G, λ) 可以表示拥有 n 个顶点的色多项式；这里，λ 用于表示颜色的数量。为了理解色多项式，我们还需要了解完全图。

完全图

然而，有些要点可以帮助我们理解完全图，具体如下：

• 如果图中的每个顶点都通过一条唯一的边连接，那么这种图就称为完全图。
• 在完全图中，图中的每个顶点都与其他顶点直接连接。
• 如果完全图包含 n 个顶点，则可以通过 (n*(n-1) /2) 来计算该图的边数。
• 在该图中，如果我们尝试找到任何顶点的度，则每个顶点的度都为 n-1，因为图中的每个顶点都与其他顶点相连。

色多项式

色多项式用于表示使用给定数量的颜色对图的顶点进行着色的方法数量。这种着色应以一种方式进行，即两个相邻的顶点不能使用相同的颜色。要开始着色，我们可以选择任何随机顶点。之后，我们移动到下一个顶点。

如果下一个顶点与第一个顶点相邻，那么第二个顶点必须使用不同的颜色进行着色。色多项式是图论领域中的一个重要工具，因为它为我们研究着色问题提供了方法。色多项式在计算机科学等各种领域有许多应用。

完全图的色多项式

为了理解这一点，我们假设有一个包含 n 个顶点的完全图。完全图的描述如下：

在此，我们假设有 λ 种颜色，可以表示为 c1, c2, c3, ……, cλ。因此，λ ≥ v。

众所周知，如果是一个完全图，那么所有顶点都必须相互连接。因此，必须为图的每个顶点分配不同的颜色。在上图中，我们从顶点 P 开始着色，因此顶点 P 有所有可用的选项，这意味着可以为顶点 P 分配 λ 种颜色。同样，顶点 Q 有所有选项，除了我们为顶点 P 使用的颜色，因此可以为顶点 Q 分配 (λ - 1) 种颜色。类似地，可以为顶点 R 分配 (λ - 2) 种颜色。当我们到达最后一个顶点时，遍历所有顶点，为最后一个顶点着色有 λ - (v - 1) 种颜色。

通过使用这种计数概念，kv 的着色方法总共有 (λ - 1)(λ - 2)(λ - 3)……(λ - v + 1) 种，其中 λ 用于表示颜色的数量。

因此，f(kv, λ) = λ(λ - 1)(λ - 2)(λ - 3)……(λ - v + 1)

色多项式示例

色多项式有许多示例。下面介绍一些示例：

示例 1

此示例包含图 G，该图有 3 个顶点 P、Q 和 R。这里，有 λ 种颜色可用于着色图中的所有这些顶点。图如下所示：

解答：在此图中，所有顶点都相互连接，因此每个顶点都必须使用不同的颜色进行着色。因此，我们从图中的任何随机顶点开始。所以，我们从顶点 P 开始。如果可能用 λ 种颜色为顶点 P 着色，那么顶点 Q 有 λ-1 种颜色可供选择，因为顶点 Q 与顶点 P 相邻。当我们转到顶点 R 时，有 λ-2 种方法可以着色。因此，对上述图 G 的着色方法总共有 λ(λ - 1)(λ - 2) 种。

因此，f(G, λ) = λ(λ - 1)(λ - 2) = λ³ - 3λ² + 2λ

我们还可以通过假设一些颜色数量并尝试为具有 3 个顶点的上述图进行着色来理解此示例。假设我们有 8 种颜色。我们可以按以下方式计算使用 8 种颜色为 3 个顶点着色的方法数量：

8*7*6 = 336 种方法

示例 2

此示例包含图 G，该图有 4 个顶点 P、Q、R 和 S。这里，有 λ 种颜色可用于着色图中的所有这些顶点。图如下所示：

解答：在上图中，我们有一个完全图，其中图中的所有顶点都相互连接，因此图中的每个顶点都必须使用不同的颜色进行着色。对上述图 G 的着色方法总共有 λ(λ - 1)(λ - 2)( λ - 3) 种。

因此，f(G, λ) = λ(λ - 1)(λ - 2)(λ - 3)

示例 3

此示例包含一个完全图 G，该图有 5 个顶点。

解答：我们有一个完全图，其中图中的所有顶点都相互连接，因此图中的每个顶点都必须使用不同的颜色进行着色。对上述图 G 的着色方法总共有 λ(λ - 1)(λ - 2)( λ - 3)( λ - 4) 种。

示例 4

此示例包含一个完全图 G，该图有 6 个顶点。

解答：我们有一个完全图，其中图中的所有顶点都相互连接，因此图中的每个顶点都必须使用不同的颜色进行着色。对上述图 G 的着色方法总共有 λ(λ - 1)(λ - 2)( λ - 3)( λ - 4)( λ - 5) 种。

因此，f(k₆, λ) = λ(λ - 1) (λ - 2) (λ - 3) ( λ - 4)( λ - 5)

色多项式的应用

假设我们有一个图 G1，我们需要计算其色数。图如下所示：

在上图中，我们有 5 个顶点，因此该图的色多项式为：

f(G1, λ) = c1 ^λC1 + c2 ^λC2 + c3 ^λC3 + c4 ^λC4 + c5 ^λC5

然而，不可能只使用 1 种颜色为图 G1 着色，所以 c1 = 0。同样，我们可以找到 c2、c3、c4 和 c5 的值，如下所示：

c2 = 0

c3 = 3! = 6

c4 = 4! * 2! = 48

c5 = 5! = 120

色多项式解释

如果我们尝试用 1 种颜色为上述图着色，则不可能，因此 c1 和 c2 等于 0，如下所示：

现在我们尝试使用 3 种颜色进行着色。因此，我们选择一个顶点 P，对于这个顶点，我们有 3 种可用的颜色选项。当我们转到下一个顶点 T 时，只有 2 种可用的颜色选项，因为顶点 T 与顶点 P 相邻。所有剩余的顶点，即 S、R、Q，只有 1 种颜色选项。因此，c3 = 3 * 2 * 1 * 1 * 1 = 3!。

现在我们尝试使用 4 种颜色进行着色。因此，我们选择一个顶点 P，对于这个顶点，我们有 4 种可用的颜色选项。当我们转到下一个顶点 T 时，只有 3 种可用的颜色选项，因为顶点 T 与顶点 P 相邻。当我们转到下一个顶点 S 时，只有 2 种可用的颜色选项，因为顶点 S 与顶点 P 和 T 相邻。当我们转到下一个顶点 R 时，只有 2 种可用的颜色选项，因为顶点 R。最后一个顶点 Q，只有 1 种可用的颜色选项。因此，c4 = 4 * 3 * 2 * 2 * 1 = 4! * 2 = 48。

现在我们尝试使用 5 种颜色进行着色。因此，我们选择一个顶点 T，对于这个顶点，我们有 5 种可用的颜色选项。当我们转到下一个顶点 S 时，只有 4 种可用的颜色选项，因为顶点 S 与顶点 T 相邻。当我们转到下一个顶点 R 时，有 3 种可用的颜色选项。当我们转到下一个顶点 Q 时，有 2 种可用的颜色选项。最后一个顶点 P，只有 1 种可用的颜色选项。因此，c5 = 5 * 4 * 3 * 2 * 1 = 5! = 120。

上述图的色多项式如下所示：

f(G1, λ) = 6 λC3 + 48 λC4 + 120 λC5

= 6* ((λ(λ-1) (λ-2)) / 3!) + 48 * ((λ(λ-1) (λ-2) (λ-3)) / 4!) + 120 * ((λ(λ-1) (λ-2) (λ-3) (λ-4)) / 5!)

= λ(λ-1) (λ-2) + 2λ(λ-1) (λ-2) (λ-3) + λ(λ-1) (λ-2) (λ-3) (λ-4)

有一个组合公式，我们将按如下方式使用它：

ⁿC_k = n! / (k! * (n-k)! )

ⁿC_k = n (n-1) (n-2) (n-3) … (n-k+1) (n-k) / k! * (n-k)!

ⁿC_k = n (n-1) (n-2) (n-3) … (n-k+1) / k!

f(G1, 1) = f(G1, 2) = 0，但 f(G1, 3) = 3(3-1) (3-2) = 3 * 2 * 1 = 6 ≠ 0

因此，上述图的色数为 3。

结论

色多项式也可以被描述为一种计数技术，在该技术中，我们计算对图进行着色的方法数量。我们可以使用一些颜色以各种方式对图进行着色。在分配颜色时，我们应该注意的一件事是，图的相邻顶点不能分配相同的颜色。

借助色多项式，我们还学习了一个称为图的色数的概念，该概念可以通过计算正确给图着色所需的最小颜色数量来计算。