Maksimumkan bilangan nod dalam graf yang terputus sambungan daripada semua nod lain

Kita mesti mencari dan mengasingkan nod yang paling kurang bersambung untuk memaksimumkan bilangan nod dalam graf yang terputus sambungan daripada semua nod lain. Strategi ini memerlukan penghapusan berulang nod dengan darjah terendah (paling bersambung) sehingga tiada lagi nod ini dapat ditemui. Hasilnya adalah untuk menyediakan bilangan maksimum nod yang dipisahkan antara satu sama lain, dengan itu sentiasa mengasingkan komponen yang berbeza dalam graf. Strategi ini mengembangkan bilangan nod dalam graf yang tidak berkaitan dengan mana-mana nod lain dengan memastikan bahawa nod yang tinggal tidak berkaitan.

Kaedah penggunaan

• Kaedah tamak

• Kaedah Set Bebas Maksimum (MIS).

Kaedah tamak

Kaedah tamak melibatkan berulang kali mengalih keluar nod darjah terendah (paling tidak bersambung) untuk memaksimumkan bilangan nod dalam graf yang tidak disambungkan kepada mana-mana nod lain. Proses ini berterusan sehingga tiada lagi nod sedemikian. Tingkatkan bilangan nod yatim dengan menghapuskan nod yang paling kurang bersambung berulang kali untuk mencipta komponen terputus dalam graf. Adalah penting untuk diingat bahawa pendekatan tamak mungkin tidak menjamin bilangan maksimum nod terputus secara konsisten dan oleh itu mungkin berbeza-beza bergantung pada susunan nod disingkirkan. Namun begitu, ia menyediakan strategi yang mudah dan berjaya untuk meningkatkan bilangan nod yang tidak bersambung dalam graf.

Algoritma

• Mulakan dari graf awal G.

• Buat senarai kosong pada permulaan untuk menyimpan nod yang terputus.

• Ulang langkah berikut sehingga tiada lagi nod boleh dipadamkan:

a. Dalam graf semasa G, kenal pasti nod dengan darjah paling rendah (paling tidak bersambung).

b. Jika terdapat berbilang nod dengan darjah minimum yang sama, pilih mana-mana nod.

c Tambahkan nod yang dipilih pada senarai nod yang terputus selepas mengeluarkannya daripada graf G.

• Teruskan carian sehingga tiada nod dengan tahap paling rendah yang tinggal.

• Bilangan nod yang saling diasingkan dalam graf diwakili oleh senarai nod yang ditarik balik yang diperoleh pada penghujung strategi.

Contoh

#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;
}

Output

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

Kaedah Set Bebas Maksimum (MIS)

Kaedah Set Bebas Maksimum (MIS) bertujuan untuk mengenal pasti subset terbesar nod yang boleh dilaksanakan di mana tiada dua nod bersebelahan (bersambung), dengan tujuan untuk meningkatkan bilangan nod dalam graf yang terputus dari semua nod lain. Ini ialah proses mencari nod dalam graf yang tidak mempunyai tepi dikongsi dan menambahkannya pada set bebas. Ini memastikan bahawa nod yang dipilih tidak disambungkan antara satu sama lain dengan memaksimumkan bilangan nod yang terputus. Semasa algoritma diteruskan, nod yang dipilih dan jirannya dialih keluar secara berulang daripada graf. Dengan mengulangi proses ini sehingga tiada lagi nod boleh ditambah pada set bebas, kami memperoleh bilangan maksimum nod yang terputus sambungan daripada setiap nod lain dalam graf.

Algoritma

• Mulakan dari graf awal G.

• Untuk menyimpan Set Bebas Maksimum (MIS), mulakan set kosong.

• Ulang langkah berikut sehingga tiada lagi nod boleh ditambahkan pada MIS:

a. Cari nod dalam graf semasa G yang tidak disambungkan kepada mana-mana nod lain melalui mana-mana tepi biasa atau jiran.

b.Sertakan nod terpilih dalam set MIS.

c. Kurangkan nod yang dipilih dan jirannya daripada graf G.

• Teruskan melakukan ini sehingga set MIS tidak lagi mengandungi sebarang nod.

Contoh

#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;
}

Output

0

Kesimpulan

Kami menggunakan dua kaedah aktif, kaedah tamak dan kaedah set bebas maksimum (MIS), untuk memaksimumkan bilangan nod dalam graf yang terputus antara satu sama lain. Kaedah tamak melibatkan penciptaan komponen yang terputus, memadamkan nod dengan tahap paling rendah berulang kali dan menambah bilangan nod yatim. Walaupun mudah, ia mungkin tidak selalu memastikan kiraan maksimum yang tepat. Kaedah MIS, sebaliknya, cuba mengasingkan nod antara satu sama lain dengan mencari subset terbesar nod yang boleh dilaksanakan tanpa sebarang sambungan bersebelahan. Kaedah MIS menyediakan cara yang lebih dipercayai untuk mencapai bilangan maksimum nod terputus secara berkaedah dengan menambah nod secara berulang pada set bebas dan mengalih keluarnya dan jirannya daripada graf.

Atas ialah kandungan terperinci Maksimumkan bilangan nod dalam graf yang terputus sambungan daripada semua nod lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!