Le nombre de composants connectés d'un graphe donné après suppression des sommets Q donnés

Après avoir supprimé Q les sommets spécifiés, le nombre de sous-graphes déconnectés créés par les sommets restants du graphique est représenté par le nombre de composants connectés. Il n'y a pas de connexions d'arêtes entre les composants individuels ; au lieu de cela, chaque composant connecté est constitué d'un ensemble de sommets reliés par une arête. En raison de la suppression des sommets Q, certains sommets peuvent devenir orphelins, provoquant l'effondrement des connexions et la formation de nouveaux composants. Cette méthode vise à déterminer combien de sous-graphes déconnectés il y aura au final. De nombreuses applications, notamment l'analyse de réseau, la recherche sur les réseaux sociaux et les méthodes d'optimisation, nécessitent une connaissance du nombre de composants connectés.

Méthode à utiliser

• Algorithme Kosaraju

• Méthode basée sur la matrice

Algorithme Kosaraju

Après avoir supprimé Q les sommets spécifiés du graphique, l'algorithme de Kosaraju est utilisé pour déterminer le nombre de composants liés dans le réseau. Il utilise la recherche en profondeur d'abord (DFS) en deux passes. Il étudie le graphe original dès la première passe pour obtenir le « temps d'achèvement » pour chaque sommet. Lors de la deuxième passe, le graphe est transposé (les directions de toutes les arêtes sont inversées) et DFS est appliqué au graphe transformé en commençant par le sommet avec le temps d'achèvement le plus long. Cette méthode détermine le nombre de composants liés dans le graphe modifié, exposant le nombre de sous-graphes brisés après la suppression du sommet en ignorant les sommets Q supprimés dans le processus.

Algorithme

• Pour stocker les sommets du canal DFS initial, créez une pile vide.

• Sur le graphique d'origine, exécutez le premier parcours DFS :

  Utilisez DFS pour explorer les composants des sommets connectés à partir des sommets inexplorés.

  Lorsque tous les sommets entourant un sommet ont été visités, Mark accède au sommet et le pousse sur la pile.

• Inversez le sens de chaque bord pour transposer la forme.

• Pour la deuxième passe DFS, créez un tableau booléen pour garder une trace des sommets visités.

• Exécutez le graphe modifié via une deuxième passe DFS :

  Supprimez tour à tour chaque sommet de la pile.

  Utilisez DFS pour explorer les composants pertinents des sommets (si aucun) ne sont pas accessibles ou détruits (pas dans Q). Tout au long du processus, Mark a visité le sommet.

• Après avoir supprimé les sommets Q, le nombre de composants connectés est égal au nombre d'appels au deuxième DFS.

• Après avoir supprimé les sommets Q, ce processus génère le nombre de composants connectés dans le réseau.

Exemple

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

void dfs1(int vertex, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& stk) {
    visited[vertex] = true;
    for (int neighbor : graph[vertex]) {
        if (!visited[neighbor])
            dfs1(neighbor, graph, visited, stk);
    }
    stk.push(vertex);
}

void dfs2(int vertex, vector<vector<int>>& transpose_graph, vector<bool>& visited) {
    visited[vertex] = true;
    for (int neighbor : transpose_graph[vertex]) {
        if (!visited[neighbor])
            dfs2(neighbor, transpose_graph, visited);
    }
}

int kosaraju(int N, vector<vector<int>>& graph, vector<vector<int>>& transpose_graph, vector<int>& Q) {
    vector<bool> visited(N + 1, false);
    stack<int> stk;

    for (int i = 1; i <= N; i++) {
        if (!visited[i])
            dfs1(i, graph, visited, stk);
    }

    fill(visited.begin(), visited.end(), false);

    for (int i = 0; i < Q.size(); i++) {
        visited[Q[i]] = true;
    }

    int count = 0;
    while (!stk.empty()) {
        int vertex = stk.top();
        stk.pop();
        if (!visited[vertex]) {
            dfs2(vertex, transpose_graph, visited);
            count++;
        }
    }

    return count;
}

int main() {
    int N = 7; 
    int M = 8; 
    int E = 2; 

    vector<vector<int>> graph(N + 1);
    vector<vector<int>> transpose_graph(N + 1);

    vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 1}, {2, 4}, {4, 5}, {5, 6}, {6, 4}, {7, 6}};

    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        transpose_graph[v].push_back(u);
    }

    vector<int> Q = {3, 4};

    int result = kosaraju(N, graph, transpose_graph, Q);
    cout << result << endl;

    return 0;
}

Sortie

5

Méthode basée sur la matrice

La matrice de contiguïté ou liste de contiguïté est utilisée pour représenter des graphiques dans des méthodes matricielles. Supprimez ensuite Q les sommets spécifiés de la matrice. Le nombre de composants connectés du graphique modifié est ensuite déterminé à l'aide d'un algorithme de parcours de graphique tel qu'une recherche en profondeur d'abord (DFS) ou une recherche en largeur d'abord (BFS). Enregistre les sommets traversés pour empêcher le retraitement. Le nombre de composants connectés dans le graphique après suppression des sommets Q correspond au nombre de fois que la méthode de parcours a été exécutée. Cette méthode peut calculer efficacement le nombre de composants de liaison pour différentes analyses graphiques et applications liées au réseau.

Algorithme

• Utilisez une matrice de contiguïté ou une liste de contiguïté pour représenter le graphique.

• Un graphique modifié est généré en supprimant les sommets Q spécifiés d'une matrice ou d'une liste.

• Définissez une variable pour suivre le nombre de composants connectés.

• Mise à jour initialement de manière itérative chaque sommet du graphique.

• Appliquez un algorithme de parcours de graphe (DFS ou BFS) à chaque sommet inexploré.

• Marquez les sommets visités pendant le parcours pour éviter le retraitement.

• Continuez à parcourir jusqu'à ce que tous les sommets liés au sommet initial aient été vus.

• Pour chaque ensemble unique de sommets interconnectés trouvés, augmentez de 1 le nombre de composants connectés dans l'équation.

• Pour accéder à chaque sommet du graphique mis à jour, répétez les étapes 5 à 8 si nécessaire.

• Après avoir supprimé les sommets requis, le nombre total de sous-graphes déconnectés dans le graphique est représenté par la valeur finale du nombre de composants connectés.

Exemple

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

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor);
        }
    }
}

int countReachableNodes(vector<vector<int>>& graph) {
    int N = graph.size();
    vector<bool> visited(N, false);
    int count = 0;

    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            count++;
        }
    }

    return count;
}

int main() {
    // Create the graph (Adjacency List representation)
    vector<vector<int>> graph = {
        {1},
        {0, 2},
        {1},
        {4},
        {3}
    };

    int reachableNodes = countReachableNodes(graph);
    cout << "Number of nodes accessible from all other nodes: " << reachableNodes << endl;

    return 0;
}

Sortie

Number of nodes accessible from all other nodes: 2

Conclusion

En résumé, une mesure clé dans l'analyse de réseau et les domaines connexes est le nombre de composants connectés restant dans le graphique après la suppression d'un certain nombre de sommets. Les méthodes matricielles et l'algorithme de Kosaraju fournissent des moyens efficaces de calculer ce décompte. Les méthodes basées sur la matrice utilisent des algorithmes de parcours de graphe tels que DFS ou BFS sur le graphe repensé pour trouver efficacement les composants liés, tandis que l'algorithme de Kosaraju utilise une recherche en profondeur d'abord dans deux parcours pour identifier les composants fortement connectés. Les deux méthodes produisent des résultats fiables même après avoir supprimé certains sommets, aidant ainsi à comprendre la connectivité et les caractéristiques structurelles du graphique. Les propriétés du graphe et les exigences spécifiques du défi actuel déterminent l'approche à utiliser.

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!