最大化圖中與所有其他節點斷開連接的節點數量

我們必須找到並隔離連接最少的節點，以便最大化圖中與所有其他節點斷開連接的節點數量。此策略需要重複消除度數最低（連接最少）的節點，直到找不到更多這些節點。這樣做的結果是提供彼此分離的最大數量的節點，從而不斷隔離圖中的不同元件。此策略透過確保其餘節點可以忽略不計地關聯，從而擴展了圖中與任何其他節點沒有關聯的節點​​的數量。

使用的方法

• 貪婪方法

• 最大獨立集合 (MIS) 方法

貪婪方法

貪婪方法涉及重複刪除度數最低（連接最少）的節點，以便最大化圖中未連接到任何其他節點的節點數量。直到不再有這樣的節點為止，這個過程將繼續進行。透過重複消除連接最少的節點來增加孤立節點的數量，以便在圖中建立斷開連接的組件。重要的是要記住，貪婪方法可能無法持續保證精確的最大斷開節點數量，因此可能會根據節點被消除的順序而變化。儘管如此，它提供了一種簡單且成功的策略來增加圖中未連接的節點的數量。

演算法

• 從初始圖 G 開始。

• 在開頭建立一個空列表來儲存斷開連接的節點。

• 重複下列步驟，直到無法刪除更多節點：

a.在目前圖 G 中，辨識度數最低（連接最少）的節點。

b.如果有多個節點具有相同的最低度數，則選擇任意節點。

c.將所選節點從圖 G 中刪除後新增至已中斷連線的節點清單中。

• 繼續搜索，直到沒有剩下最低度數的節點。

• 圖表中相互隔離的節點數量由策略結束時獲得的撤回節點清單表示。

範例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Graph {
   int V;
   vector<vector<int>> adj;

   Graph(int vertices) : V(vertices) {
      adj.resize(V, vector<int>());
   }

   void addEdge(int u, int v) {
      adj[u].push_back(v);
      adj[v].push_back(u);
   }

   int findLowestDegreeNode() {
      int minDegree = V + 1;
      int node = -1;

      for (int i = 0; i < V; ++i) {
         if (adj[i].size() < minDegree) {
            minDegree = adj[i].size();
            node = i;
         }
      }

      return node;
   }

   vector<int> getDisconnectedNodes() {
      vector<int> disconnected;
      while (true) {
         int node = findLowestDegreeNode();
         if (node == -1)
            break;

         disconnected.push_back(node);
         for (int neighbor : adj[node]) {
            adj[neighbor].erase(remove(adj[neighbor].begin(), adj[neighbor].end
(), node), adj[neighbor].end());
         }
         adj[node].clear();
      }
      return disconnected;
   }
};

void printGraph(Graph& G) {
   for (int i = 0; i < G.V; ++i) {
      cout << "Node " << i << " : ";
      for (int neighbor : G.adj[i]) {
         cout << neighbor << " ";
      }
      cout << endl;
   }
}

int main() {
   Graph G(5);
   G.addEdge(0, 1);
   G.addEdge(0, 2);
   G.addEdge(1, 2);
   G.addEdge(3, 4);

   cout << "Initial Graph:" << endl;
   printGraph(G);

   G.getDisconnectedNodes();

   cout << "Graph after removing nodes:" << endl;
   printGraph(G);

   return 0;
}

輸出

Initial Graph:
Node 0 : 1 2 
Node 1 : 0 2 
Node 2 : 0 1 
Node 3 : 4 
Node 4 : 3 

最大獨立集合 (MIS) 方法

最大獨立集 (MIS) 方法旨在識別其中沒有兩個節點相鄰（連接）的節點的最大可行子集，目的是增加圖中與所有其他節點斷開連接的節點數量。尋找圖中沒有共享邊的節點並將它們新增至獨立集中的過程就是這樣。透過最大化斷開連接的節點數量，這可以確保所選節點不會相互連接。隨著演算法的繼續，選定的節點及其鄰居將從圖中迭代地刪除。透過重複此過程，直到無法將更多節點新增至獨立集中，我們獲得了圖中與每個其他節點斷開連接的節點的最大數量。

演算法

• 從初始圖 G 開始。

• 要儲存最大獨立集 (MIS)，請初始化一個空集合。

• 重複下列步驟，直到無法在 MIS 上新增更多節點：

a.定位目前圖 G 中的一個節點，該節點未透過任何公共邊或鄰居連接到任何其他節點。

b.將選定的節點包含在 MIS 集中。

c.從圖 G 中減去所選節點及其鄰居。

• 繼續執行此操作，直到 MIS 集不再包含任何節點。

範例

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

class Graph {
private:
   vector<set<int>> adjacencyList;
public:
   Graph(int numNodes) : adjacencyList(numNodes) {}
   void addEdge(int u, int v);
   set<int> findIndependentSet();
};

void Graph::addEdge(int u, int v) {
   adjacencyList[u].insert(v);
   adjacencyList[v].insert(u);
}

set<int> Graph::findIndependentSet() {
   set<int> independentSet;
   vector<bool> included(adjacencyList.size(), false);
   
   while (true) {
      int nodeToAdd = -1;
      for (int i = 0; i < adjacencyList.size(); ++i) {
         if (!included[i]) {
            bool canAdd = true;
            for (const int& neighbor : adjacencyList[i]) {
               if (included[neighbor]) {
                  canAdd = false;
                  break;
               }
            }
            if (canAdd) {
               nodeToAdd = i;
               break;
            }
         }
      }
      if (nodeToAdd == -1) {
         break;
      }
      independentSet.insert(nodeToAdd);
      included[nodeToAdd] = true;
      for (const int& neighbor : adjacencyList[nodeToAdd]) {
         included[neighbor] = true;
      }
   }
   return independentSet;
}

int main() {
   // Example graph with 7 nodes and 6 edges
   Graph graph(7);
   graph.addEdge(0, 1);
   graph.addEdge(0, 2);
   graph.addEdge(1, 3);
   graph.addEdge(1, 4);
   graph.addEdge(2, 5);
   graph.addEdge(2, 6);

   set<int> maxIndependentSet = graph.findIndependentSet();
   for (const int& node : maxIndependentSet) {
      cout << node << " ";
   }
   cout << endl;

   return 0;
}

輸出

0

結論

我們使用兩種主動方法，即貪婪方法和最大獨立集 (MIS) 方法，來最大化圖中相互斷開的節點數量。貪婪方法涉及創建斷開連接的組件、重複刪除度數最低的節點以及增加孤立節點的數量。雖然簡單，但它可能不會總是確保精確的最大計數。另一方面，MIS 方法試圖透過定位沒有任何相鄰連接的最大可行節點子集來將節點彼此隔離。 MIS 方法提供了一種更可靠的方法，透過迭代地將節點新增至獨立集中並將它們及其鄰居從圖中刪除，有條不紊地達到斷開節點的最大數量。

以上是最大化圖中與所有其他節點斷開連接的節點數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！