Maximize the number of nodes in the graph that are disconnected from all other nodes

We must find and isolate the least connected nodes in order to maximize the number of nodes in the graph that are disconnected from all other nodes. This strategy requires repeated elimination of nodes with the lowest degree (least connected) until no more of these nodes can be found. The result of this is to provide a maximum number of nodes that are separated from each other, thus constantly isolating different components in the graph. This strategy expands the number of nodes in the graph that are not related to any other nodes by ensuring that the remaining nodes are negligibly related.

usage instructions

• Greedy method

• Maximum independent set (MIS) method

Greedy method

The greedy method involves repeatedly removing the lowest degree (least connected) nodes in order to maximize the number of nodes in the graph that are not connected to any other node. The process continues until there are no more such nodes. Increase the number of orphan nodes by repeatedly eliminating the least connected nodes to create disconnected components in the graph. It is important to remember that the greedy approach may not consistently guarantee the exact maximum number of disconnected nodes and therefore may vary depending on the order in which nodes are eliminated. Nonetheless, it provides a simple and successful strategy to increase the number of unconnected nodes in the graph.

algorithm

• Start from the initial graph G.

• Create an empty list at the beginning to store disconnected nodes.

• Repeat the following steps until no more nodes can be deleted:

a. In the current graph G, identify the node with the lowest degree (least connected).

b. If there are multiple nodes with the same minimum degree, select any node.

c. Add the selected node to the disconnected node list after removing it from the graph G.

• Continue searching until there is no node with the lowest degree left.

• The number of mutually isolated nodes in the graph is represented by the list of withdrawn nodes obtained at the end of the strategy.

Example

#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 

Maximal independent set (MIS) method

The Maximum Independent Set (MIS) method aims to identify the largest feasible subset of nodes in which no two nodes are adjacent (connected), with the goal of increasing the number of nodes in the graph that are disconnected from all other nodes. This is the process of finding nodes in the graph that have no shared edges and adding them to an independent set. This ensures that selected nodes are not connected to each other by maximizing the number of disconnected nodes. As the algorithm continues, selected nodes and their neighbors are iteratively removed from the graph. By repeating this process until no more nodes can be added to the independent set, we obtain the maximum number of nodes that are disconnected from every other node in the graph.

algorithm

• Start from the initial graph G.

• To store a maximum independent set (MIS), initialize an empty set.

• Repeat the following steps until no more nodes can be added to the MIS:

a. Locate a node in the current graph G that is not connected to any other node through any common edges or neighbors.

b.Include selected nodes in the MIS set.

c. Subtract the selected node and its neighbors from the graph G.

• Continue doing this until the MIS set no longer contains any nodes.

Example

#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

in conclusion

We use two active methods, the greedy method and the maximum independent set (MIS) method, to maximize the number of nodes in the graph that are disconnected from each other. Greedy methods involve creating disconnected components, repeatedly deleting nodes with the lowest degree, and increasing the number of orphan nodes. Although simple, it may not always ensure an accurate maximum count. MIS methods, on the other hand, attempt to isolate nodes from each other by locating the largest feasible subset of nodes without any adjacent connections. The MIS method provides a more reliable way to methodically reach the maximum number of disconnected nodes by iteratively adding nodes to the independent set and removing them and their neighbors from the graph.

The above is the detailed content of Maximize the number of nodes in the graph that are disconnected from all other nodes. For more information, please follow other related articles on the PHP Chinese website!