在完美图中寻找最大团

Question

如何快速找到一个有大约100个顶点的完美图中（具有至少1条弦的奇数环），最大团的大小算法？是否有比暴力更简单的方法，因为这是一个完美图，应该有多项式时间解决方案。但我找不到算法。

贪心着色是否在所有完美图中都能给出最优着色？

- copperhead

---

我尝试了几种方法，但它们都太慢了。 - copperhead

刚在维基百科上发现了这个：在所有完美图中，图着色问题、最大团问题和最大独立集问题都可以在多项式时间内解决（Grötschel，Lovász＆Schrijver 1988）Grötschel，Martin; Lovász，László; Schrijver，Alexander（1988）。几何算法和组合优化。Springer-Verlag。特别是第9章“图中的稳定集”，第273-303页。 - yogsototh

Answer 1

100个顶点？用Cliquer可以在几秒钟内（也许是几分之一秒）轻松暴力解决。

http://users.tkk.fi/pat/cliquer.html

- Chad Brewbaker

---

你能否用简单的术语解释一下算法（我已经看过文档）？ - copperhead

当然。首先，Cliquer定义了顶点的排列。我认为默认情况下，它按照输入中使用的任何顺序进行排序。其次，cliquer迭代地在集合[i...n]中查找最大的团，从i=n-1到i=1。在此过程中，它记住了迄今为止找到的最大团，并且在测试新团时，当从先前计算的团大小变得明显时，它会修剪搜索，以便该搜索路径无法产生更大的团。 - Chad Brewbaker

Answer 2

请参见296页，通过一些工作，您应该编写正确的线性规划约束来解决这个问题。

http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization

- yogsototh

---

+1：只有回答涉及完美图的才是正确的，其中团问题属于P类问题。 - Aryabhatta

Answer 3

回答第二个问题：

一般来说，贪心着色并不能在所有完美图中给出最优着色。一个简单的例子是，对于一个完美图，按照顶点字母表顺序[a,b,c,d]进行贪心着色，边{ac, bc, db}将产生一个2可着色图的3着色。如果你想要强制贪心着色以BFS方式处理顶点，那么同样的图形，源顶点s与a、b、c、d相邻，并从s开始，将类似地产生一个3可着色图的4着色。

有一类称为“完全可排序”的完美图，可以按照某种方式对其顶点进行排序，使得按照该顺序贪心着色，保证产生最优着色-不仅适用于图本身-而且该顺序对于每个诱导子图都给出最优贪心着色。

其中一个问题是，即使给定了一个完全可排序的图，找到这样一个完美的顺序仍然是NP难题。

另一方面，有几个完全可排序图的子类，可以很容易地找到一个完美的顺序（因此贪心着色保证是最优的）。特别地，半同构图这个类具有这样的属性，即任何顶点排序都是一个完美的顺序（意味着对于半同构图的任何贪心着色都保证是最优的）。

- JimN