图形的3色（多项式时间）？ [英] 3-colouring of a graph (polynomial time)?

问题描述

我们可以在多项式时间内为图形着色3种颜色吗？我读到用2

颜色为图形着色很容易，但是用3种不同颜色（没有两个顶点具有
相同颜色）为图形着色是np困难的。我想知道是否有一个魔术盒对'A

图在多项式时间内是3色的？表示'是'。如果它说'是'，它将如何在
$中解决它。 b $ b多项式时间？有任何想法吗 ？

解决方案

向您的图形添加3个新顶点，称为红色/绿色/蓝色，每个顶点都与其他2个顶点相连，但是没有其他内容。 / p>

然后为图形中的每个顶点：

1. 将顶点连接到红色并绿色，如果结果图是3色


2. 否则，将顶点连接到绿色和蓝色，如果结果图是3色


3. ，否则，将顶点连接顶点为红色和蓝色（通过构建，结果图必须为3色）

在此过程结束时，您将确定一个每个顶点的颜色（未连接的颜色）。

这是O（N * magic），其中magic是魔术盒的复杂度。

p>

Can we colour a graph in 3 colours in polynomial time? I read that colouring a graph with 2
colours is easy,but colouring a graph with 3 different colours(No two vertices have the
same color) is np-hard.However,I wonder if there is a magic box that says 'yes' for 'A
graph being 3-colourable in polynomial time?'.If it says 'yes' how would it solve it in
polynomial time? Any Ideas ?

解决方案

Add 3 new vertices to your graph called red/green/blue, each connected to the other 2 but nothing else.

Then for each vertex in your graph:

1. Connect the vertex to red and green if the resulting graph is 3 colourable
2. Otherwise, connect the vertex to green and blue if the resulting graph is 3 colourable
3. Otherwise, connect the vertex to red and blue (by construction the resulting graph must be 3 colourable)

At the end of this process you will have identified a colour for each vertex (the colour that it is not connected to).

This is O(N*magic) where magic is the complexity of your magic box.

这篇关于图形的3色（多项式时间）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！