给定图的顶点的k-着色计算（k-​​1） - 着色

Question

图的着色顶点是NP完全的常见知识。 也知道有高效的贪婪算法可以得到一个近似的解决方案。 为什么不使用这些随机贪婪算法来计算k种颜色的着色，然后使用一些较慢的算法来减少k？

在我的情况下，我知道足够的颜色图G的最小数量 - 让我们把它称为K.我也设法实现SL算法给我（K + 2） - 着色。一种颜色只用于给一个顶点着色，所以我设法通过手动重新着色一些其他节点来移除它。因此，我有（K + 1）着色，并希望编写一个算法，将K减少1（或更确切地说K + 1）。

我试着手动做 - 我发现一种颜色用于用相同颜色着色的最小数量的顶点，并将此颜色的用途减少到3.我必须仅重新着色3个节点。

一个想法是进行3次递归调用 - 每个调用颜色严重的节点。让我们来分析递归函数对节点v所要做的事情。它必须检查除v之外的颜色和我们想要移除的颜色。因此，对于每种颜色c，应该将v的颜色设置为c，并对与v相邻并且具有颜色c的每个节点进行递归调用。检查所有颜色后，我们应该检索v的旧颜色并重新设置。还有一种优化可能不会尝试将v的颜色更改为其邻居的x以上的颜色（因为递归树会太深） - 但对于太小的x，它可能根本无法改变颜色。

另一个想法是检查颜色可以改变的节点（而不是我们想要移除的颜色），以便它不会与邻居的颜色发生冲突。并进行递归调用来更改其他节点的颜色，直到我们想要移除的一种颜色将被重新着色。

这是我实现其目的是在n < 90工作，但是似乎并没有终结（500分钟执行的）第一个算法：

#include<stdio.h> 
#include<assert.h> 
#include<vector> 
using namespace std; 

vector<int> graph[99]; 
int hash[10009], color[99]; 
const int colors = 9, color_to_change = 7; 

void change_color(int v) 
{ 
    int tmp = color[v], count; 
    for(int i = 1; i <= colors; ++i) 
    { 
     count = 0; 
     for(int j = 0; j < graph[v].size(); ++j) 
      count += color[graph[v][j]] == i; 
     if(!count) 
     { 
      color[v] = i; 
      return; 
     } 
     if(count < 4 && i != color_to_change && i != color[v]) 
     { 
      color[v] = i; 
      for(int j = 0; j < graph[v].size(); ++j) 
       if(color[graph[v][j]] == i) 
        change_color(graph[v][j]); 
     } 
    } 
    color[v] = tmp; 
} 

int main() 
{ 
    int n, m, a, b, max = 0, j = -1; 

    scanf("%d%d", &n, &m); 
    while(m--) 
    { 
     scanf("%d%d", &a, &b); 
     assert(a != b); 
     if(hash[a*100+b] || hash[b*100+a]) 
      continue; 
     assert(a*100+b < 10000 && b*100+a < 10000); 
     hash[a*100+b] = hash[b*100+a] = 1; 
     graph[a].push_back(b); 
     graph[b].push_back(a); 
    } 
    for(int i = 1; i <= n; ++i) 
     scanf("%d", &color[i]); 
    for(int i = 1; i <= n; ++i) 
     if(color[i] == color_to_change) 
      change_color(i); 
    for(int i = 1; i <= n; ++i) 
     printf("%d ", color[i]); 
    return 0; 
} 

任何想法如何使它更快吗？

Answer 1

我只是简单地看了一下代码，并且读了你的解释，但是看起来你进入了一个无限循环，在邻居之间来回切换。您需要在每个节点中存储一个标志，以表明它目前正在重新着色，并且只会递归到那些当前未正在重新着色的邻居中。

但是 - 这种算法在最坏的情况下看起来像是指数函数 - 我敢肯定，有些情况下K图不能在不改变某些大部分图的情况下重新着色到K-1图，即使颜色K的节点数只有1个。

下面是一个简单拓扑图的示例。它清楚地表明它可以是两种颜色（R，G），并且我们有使用（R，G，B）的三色版本。正确重新着色的唯一方法是更改​​大约1/2个节点的颜色，最终以下面的其他版本之一。 ()表示颜色B的单个节点，[]表示需要重新着色的部分。

3 colour version : R-G-R-G-R-G-(B)-R-G-R-G-R-G-R 
2 colour version 1: [R-G-R-G-R-G- R]-G-R-G-R-G-R-G 
2 colour version 2: G-R-G-R-G-R-[G -R-G-R-G-R-G-R] 

这意味着您的（潜在指数）搜索的最小深度可能超过节点数的1/2。这可能会损害合理的性能时间（或者可能不取决于我猜想的图形的拓扑结构。）