3-著色問題是NP完全問題

---

3-著色是一個圖論中典型的NP完全問題，其目標是確定給定的圖是否可以使用三種顏色進行著色，使得任意兩個相鄰的頂點不具有相同的顏色。該問題被歸類為NP完全問題，這意味著沒有已知的有效演算法可以解決所有情況，但檢查一個潛在的解決方案可以在多項式時間內完成。許多其他NP完全問題可以歸約到3-著色，這表明了其計算複雜性和在理解更廣泛的NP完全問題類別中的重要性。因此，3-著色在計算複雜性和演算法設計的研究中發揮著重要作用。

使用的方法

• 回溯法

• 精確覆蓋3-集問題

• 從3-SAT歸約

回溯法

回溯法是一種系統性的演算法方法，用於透過逐步構建潛在的解決方案並放棄不滿足特定條件的解決方案來解決組合問題。它探索所有可能的路徑以有效地找到有效的解決方案。回溯法可以透過遞迴或使用顯式棧來實現。

演算法

• 從所有頂點的空顏色分配開始。

• 選擇一個未著色的頂點，併為其分配一個顏色（1、2或3）。

• 遞迴地將步驟2應用於當前頂點的所有未著色的鄰居。

• 如果在任何時候，一個頂點沒有有效的顏色不與它的鄰居衝突，則回溯並嘗試為前一個頂點嘗試不同的顏色。

• 重複步驟2-4，直到所有頂點都被著色或確定不存在有效的著色。

示例

#include <iostream>
#include <vector>
using namespace std;

const int MAX_VERTICES = 100; 

vector<int> graph[MAX_VERTICES];
int color[MAX_VERTICES];

bool isBipartiteUtil(int v, int c) {
   color[v] = c;
   for (int u : graph[v]) {
      if (color[u] == c)
         return false;
      if (color[u] == 0 && !isBipartiteUtil(u, -c))
         return false;
   }
   return true;
}

bool isBipartite(int numVertices) {
   for (int i = 0; i < numVertices; ++i) {
      if (color[i] == 0 && !isBipartiteUtil(i, 1))
         return false;
   }
   return true;
}

int main() {
   int numVertices = 4;
   graph[0].push_back(1);
   graph[0].push_back(3);
   graph[1].push_back(0);
   graph[1].push_back(2);
   graph[2].push_back(1);
   graph[2].push_back(3);
   graph[3].push_back(0);
   graph[3].push_back(2);

   if (isBipartite(numVertices)) {
      cout << "Graph is Bipartite.
";
   } else {
      cout << "Graph is not Bipartite.
";
   }

   return 0;
}

輸出

Graph is Bipartite.

精確覆蓋3-集問題

精確覆蓋3-集問題（X3C）是精確覆蓋問題的一個特定變體，精確覆蓋問題是一個NP完全問題。在X3C中，我們給定一個集合X，它包含n個元素，以及一個集合C，它包含X的3個元素子集。問題是是否存在一個精確覆蓋，即C的一個子集C'，使得X中的每個元素恰好出現在C'中的一個子集中。換句話說，我們需要找到一組不相交的3-集，這些3-集恰好覆蓋X中的所有元素一次。

為了展示從3-SAT到X3C的歸約，我們將說明如何從給定的3-SAT例項構建X3C的例項。

演算法

• 從給定的圖構建一個精確覆蓋3-集問題。

• 使用解決精確覆蓋問題的演算法來找到覆蓋所有頂點的一組3-集。

• 如果存在解，則檢查每個3-集是否包含唯一的頂點（沒有頂點重複），並且每個頂點恰好出現在一個3-集中。

• 如果所有條件都滿足，則圖可以被3-著色。否則，它不能被3-著色。

示例

#include <iostream>
#include <vector>

bool hasDefiniteCover(const std::vector<std::vector<int>>& chart) {
   return false;
}

int main() {
   std::vector<std::vector<int>> chart = {
      {1, 2, 3},
      {4, 5, 6},
      {7, 8, 9},
   };

   bool definiteCoverExists = hasDefiniteCover(chart);
   std::cout << "Definite Cover Exists: " << std::boolalpha << definiteCoverExists << std::endl;

   return 0;
}

輸出

Definite Cover Exists: false

從3-SAT歸約

在計算複雜性理論中，“歸約”是指將一個問題（源問題）轉換為另一個問題（目標問題）的過程，以便如果我們能夠有效地解決目標問題，我們也能夠有效地解決源問題。其思想是表明源問題不比目標問題更難。

3-SAT是一個著名的NP完全問題。它是一個判定問題，其中輸入由一個合取正規化（CNF）的布林公式組成，每個子句包含三個文字，問題是是否存在一個對變數的真值賦值，使得整個公式為真。

為了展示從3-SAT到另一個問題的歸約，讓我們假設一個已知問題，稱為頂點覆蓋（VC）。頂點覆蓋也是一個NP完全問題，其中輸入是一個無向圖G和一個數字k，問題是是否存在一個大小最多為k的頂點覆蓋。頂點覆蓋是頂點的子集，使得圖中的每條邊都與該子集中的至少一個頂點相關聯。

演算法

• 給定一個具有變數和子句的3-SAT問題，建立一個圖，其中每個變數對應一個頂點。

• 連線同一個子句中變數對應的頂點，以及關聯子句中的變數（例如，如果一個子句包含（x1 v x2 v ¬x3），則連線對應於x1、x2和¬x3的頂點）。

• 檢查生成的圖是否可以3-著色。

• 如果圖可以3-著色，則3-SAT問題有解，反之亦然。

示例

#include <iostream>
#include <vector>

using namespace std;

bool isGraph3Colorable(const vector<vector<int>>& graph, int numVertices) {
   vector<int> colors(numVertices, -1);

   for (int vertex = 0; vertex < numVertices; ++vertex) {
      if (colors[vertex] == -1) {
         colors[vertex] = 0;
         vector<int> queue;
         queue.push_back(vertex);

         while (!queue.empty()) {
            int current = queue.back();
            queue.pop_back();

            for (int neighbor : graph[current]) {
               if (colors[neighbor] == -1) {
                  colors[neighbor] = 1 - colors[current];
                  queue.push_back(neighbor);
               } else if (colors[neighbor] == colors[current]) {
                  return false;
               }
            }
         }
      }
   }

   return true;
}

vector<vector<int>> createDiagram(int numVariables, const vector<vector<int>>& clauses) {
   vector<vector<int>> diagram(numVariables * 3);

   for (int i = 0; i < clauses.size(); ++i) {
      int x = abs(clauses[i][0]) - 1;
      int y = abs(clauses[i][1]) - 1;
      int z = abs(clauses[i][2]) - 1;

      int xi = (clauses[i][0] < 0) ? x + 2 * numVariables : x;
      int yi = (clauses[i][1] < 0) ? y + 2 * numVariables : y;
      int zi = (clauses[i][2] < 0) ? z + 2 * numVariables : z;

      diagram[xi].push_back(yi);
      diagram[xi].push_back(zi);
      diagram[yi].push_back(xi);
      diagram[yi].push_back(zi);
      diagram[zi].push_back(xi);
      diagram[zi].push_back(yi);
   }

   return diagram;
}

int main() {
   int numVariables = 3;
   vector<vector<int>> clauses = {{-1, 2, -3}, {1, -2, 3}, {2, 3, 1}};

   vector<vector<int>> diagram = createDiagram(numVariables, clauses);

   if (isGraph3Colorable(diagram, numVariables * 3)) {
      cout << "The diagram is 3-colorable. The 3-SAT issue has a solution." << endl;
   } else {
      cout << "The diagram is not 3-colorable. The 3-SAT issue does not have a solution." << endl;
   }

   return 0;
}

輸出

The diagram is not 3-colorable. The 3-SAT issue does not have a solution.

結論

3-著色問題已知是NP完全的，這意味著沒有已知的針對所有例項的多項式時間演算法來解決它。上面描述的方法本質上是指數級的，它們的複雜度隨著圖的大小迅速增加。因此，對於大型圖，在合理的時間內找到最佳的3-著色可能是不可能的。然而，這些方法對於理解計算複雜性的理論方面以及不同NP完全問題之間的關係至關重要。