Maximiser le nombre de nœuds dans le graphique qui sont déconnectés de tous les autres nœuds

Nous devons trouver et isoler les nœuds les moins connectés afin de maximiser le nombre de nœuds dans le graphique qui sont déconnectés de tous les autres nœuds. Cette stratégie nécessite une élimination répétée des nœuds ayant le degré le plus bas (les moins connectés) jusqu'à ce qu'aucun de ces nœuds ne puisse être trouvé. Le résultat est de fournir un nombre maximum de nœuds séparés les uns des autres, isolant ainsi constamment les différents composants du graphe. Cette stratégie augmente le nombre de nœuds dans le graphique qui ne sont liés à aucun autre nœud en garantissant que les nœuds restants sont négligeablement liés.

Méthode à utiliser

• Méthode gourmande

• Méthode de l'ensemble indépendant maximum (MIS)

Méthode gourmande

La méthode gourmande consiste à supprimer à plusieurs reprises les nœuds du degré le plus bas (les moins connectés) afin de maximiser le nombre de nœuds dans le graphique qui ne sont connectés à aucun autre nœud. Le processus se poursuit jusqu'à ce qu'il n'y ait plus de tels nœuds. Augmentez le nombre de nœuds orphelins en éliminant à plusieurs reprises les nœuds les moins connectés pour créer des composants déconnectés dans le graphique. Il est important de se rappeler que l’approche gloutonne peut ne pas garantir systématiquement le nombre maximum exact de nœuds déconnectés et peut donc varier en fonction de l’ordre dans lequel les nœuds sont éliminés. Néanmoins, il fournit une stratégie simple et efficace pour augmenter le nombre de nœuds non connectés dans le graphique.

Algorithme

• Partez du graphique initial G.

• Créez une liste vide au début pour stocker les nœuds déconnectés.

• Répétez les étapes suivantes jusqu'à ce qu'aucun nœud ne puisse plus être supprimé :

a. Dans le graphique G actuel, identifiez le nœud avec le degré le plus bas (le moins connecté).

b. S'il existe plusieurs nœuds avec le même degré minimum, sélectionnez n'importe quel nœud.

c. Ajoutez le nœud sélectionné à la liste des nœuds déconnectés après l'avoir supprimé du graphique G.

• Continuez la recherche jusqu'à ce qu'il ne reste plus de nœuds avec le degré le plus bas.

• Le nombre de nœuds mutuellement isolés dans le graphique est représenté par la liste des nœuds retirés obtenue à la fin de la stratégie.

Exemple

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

Sortie

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

Méthode de l'ensemble indépendant maximum (MIS)

La méthode Maximum Independent Set (MIS) vise à identifier le plus grand sous-ensemble possible de nœuds dans lequel aucun nœud n'est adjacent (connecté), dans le but d'augmenter le nombre de nœuds dans le graphique qui sont déconnectés de tous les autres nœuds. Il s'agit du processus consistant à rechercher des nœuds dans le graphique qui n'ont pas d'arêtes partagées et à les ajouter à un ensemble indépendant. Cela garantit que les nœuds sélectionnés ne sont pas connectés les uns aux autres en maximisant le nombre de nœuds déconnectés. Au fur et à mesure que l'algorithme progresse, les nœuds sélectionnés et leurs voisins sont supprimés de manière itérative du graphique. En répétant ce processus jusqu'à ce qu'aucun nœud ne puisse être ajouté à l'ensemble indépendant, nous obtenons le nombre maximum de nœuds déconnectés de tous les autres nœuds du graphique.

Algorithme

• Partez du graphique initial G.

• Pour stocker l'ensemble indépendant maximum (MIS), initialisez un ensemble vide.

• Répétez les étapes suivantes jusqu'à ce qu'aucun nœud ne puisse être ajouté au MIS :

a. Localisez un nœud dans le graphe actuel G qui n'est connecté à aucun autre nœud par des arêtes communes ou des voisins.

b.Inclure les nœuds sélectionnés dans l'ensemble MIS.

c. Soustrayez le nœud sélectionné et ses voisins du graphique G.

• Continuez ainsi jusqu'à ce que l'ensemble MIS ne contienne plus aucun nœud.

Exemple

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

Sortie

0

Conclusion

Nous utilisons deux méthodes actives, la méthode gloutonne et la méthode de l'ensemble indépendant maximum (MIS), pour maximiser le nombre de nœuds dans le graphique qui sont déconnectés les uns des autres. Les méthodes gourmandes impliquent la création de composants déconnectés, la suppression répétée de nœuds de degré le plus bas et l'augmentation du nombre de nœuds orphelins. Bien que simple, cela ne garantit pas toujours un décompte maximum précis. Les méthodes MIS, quant à elles, tentent d'isoler les nœuds les uns des autres en localisant le plus grand sous-ensemble possible de nœuds sans aucune connexion adjacente. La méthode MIS fournit un moyen plus fiable d'atteindre méthodiquement le nombre maximum de nœuds déconnectés en ajoutant de manière itérative des nœuds à l'ensemble indépendant et en les supprimant ainsi que leurs voisins du graphique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!