图形数据结构教程7.图形着色问题

在本教程中，我们将学习2色图问题

在一般的图形着色或边缘着色问题中，我们需要以一种方式将颜色分配给顶点，使得没有边缘链接具有相同颜色的两个顶点。

考虑以下图像集：

这里的图a是有效的。但是图b是无效的，因为在顶点“ b”和顶点“ c”之间存在具有相同颜色的边。

如何解决呢？

一个简单的解决方案是为每个顶点设置不同的颜色。但是，目标是使用尽可能少的颜色。

图形着色算法在许多领域中都使用，包括调度应用程序。

现在我们来讨论2色图问题。现在需要研究这个问题吗？

在上一节中，我们了解了二部图。为了使图成为二部图，它应该是2色图。因此，如果我们可以证明一个图只能用两种颜色上色，那么该图就是二部图。

那么，如何仅使用两种颜色为图形着色呢？

这很简单。选择一个起始顶点，并为其指定颜色“红色”。

现在，使其所有邻居都具有其他颜色，例如“绿色”。

并且所有相邻的顶点均为“绿色”色顶点，将其着色为“红色”。

继续直到顶点被着色为止。

下图显示了2种颜色图表问题的分步过程。

在上图中，我们仅使用2种颜色对图形进行了着色。

因此，要检查图是否为二分图，我们将检查图是否为2可着色，并且它也不应包含奇数循环。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：