Die Anzahl der verbundenen Komponenten eines bestimmten Graphen nach dem Löschen der angegebenen Q-Eckpunkte

Nach dem Entfernen von Q angegebenen Scheitelpunkten wird die Anzahl der nicht verbundenen Untergraphen, die von den verbleibenden Scheitelpunkten im Diagramm erstellt werden, durch die Anzahl der verbundenen Komponenten dargestellt. Es gibt keine Kantenverbindungen zwischen einzelnen Komponenten; stattdessen besteht jede verbundene Komponente aus einer Ansammlung von Eckpunkten, die durch eine Kante verbunden sind. Durch das Entfernen von Q-Scheitelpunkten können einige Eckpunkte verwaist werden, was dazu führt, dass Verbindungen zusammenbrechen und neue Komponenten entstehen. Mit dieser Methode soll ermittelt werden, wie viele nicht verbundene Teilgraphen es am Ende geben wird. Viele Anwendungen, darunter Netzwerkanalyse, soziale Netzwerkforschung und Optimierungsmethoden, erfordern Kenntnisse über die Anzahl der verbundenen Komponenten.

Anwendungsmethode

• Kosaraju-Algorithmus

• Matrixbasierte Methode

Kosaraju-Algorithmus

Nachdem Q spezifizierte Eckpunkte aus dem Diagramm entfernt wurden, wird der Kosaraju-Algorithmus verwendet, um die Anzahl der verknüpften Komponenten im Netzwerk zu bestimmen. Es verwendet die Tiefensuche (DFS) in zwei Durchgängen. Im ersten Durchgang wird der ursprüngliche Graph untersucht, um die „Abschlusszeit“ für jeden Scheitelpunkt zu ermitteln. Im zweiten Durchgang wird der Graph transponiert (die Richtungen aller Kanten werden umgekehrt) und DFS wird auf den transformierten Graphen angewendet, beginnend mit dem Scheitelpunkt mit der längsten Fertigstellungszeit. Diese Methode bestimmt die Anzahl der verknüpften Komponenten im geänderten Diagramm und legt die Anzahl der defekten Untergraphen nach dem Löschen von Scheitelpunkten offen, indem gelöschte Q-Scheitelpunkte im Prozess ignoriert werden.

Algorithmus

• Um die Eckpunkte des anfänglichen DFS-Kanals zu speichern, erstellen Sie einen leeren Stapel.

• Führen Sie im Originaldiagramm die erste DFS-Durchquerung aus:

  Verwenden Sie DFS, um Komponenten verbundener Scheitelpunkte ausgehend von unerforschten Scheitelpunkten zu erkunden.

  Wenn alle einen Scheitelpunkt umgebenden Scheitelpunkte besucht wurden, greift Mark auf den Scheitelpunkt zu und schiebt ihn auf den Stapel.

• Kehren Sie die Richtung jeder Kante um, um die Form zu vertauschen.

• Erstellen Sie für den zweiten DFS-Durchlauf ein boolesches Array, um die besuchten Eckpunkte zu verfolgen.

• Führen Sie das geänderte Diagramm durch einen zweiten DFS-Durchlauf:

  Entfernen Sie nacheinander jeden Scheitelpunkt vom Stapel.

  Verwenden Sie DFS, um die relevanten Komponenten der Scheitelpunkte zu untersuchen (falls keine vorhanden sind), auf die nicht zugegriffen wird oder die nicht zerstört werden (nicht in Q). Während des gesamten Prozesses besuchte Mark den Scheitelpunkt.

• Nach dem Entfernen von Q-Eckpunkten entspricht die Anzahl der verbundenen Komponenten der Anzahl der Aufrufe des zweiten DFS.

• Nach dem Entfernen von Q-Scheitelpunkten generiert dieser Prozess die Anzahl der verbundenen Komponenten im Netzwerk.

Beispiel

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

Ausgabe

5

Matrixbasierte Methode

Adjazenzmatrix oder Adjazenzliste wird verwendet, um Diagramme in Matrix-basierten Methoden darzustellen. Entfernen Sie dann Q angegebene Eckpunkte aus der Matrix. Die Anzahl der verbundenen Komponenten des geänderten Graphen wird dann mithilfe eines Graph-Traversal-Algorithmus wie der Tiefensuche (DFS) oder der Breitensuche (BFS) bestimmt. Zeichnet überquerte Scheitelpunkte auf, um eine erneute Verarbeitung zu verhindern. Die Anzahl der verbundenen Komponenten im Diagramm nach dem Entfernen von Q-Eckpunkten entspricht der Häufigkeit, mit der die Traversierungsmethode ausgeführt wurde. Mit dieser Methode kann die Anzahl der Verbindungskomponenten für verschiedene Diagrammanalysen und netzwerkbezogene Anwendungen effizient berechnet werden.

Algorithmus

• Verwenden Sie eine Adjazenzmatrix oder eine Adjazenzliste, um das Diagramm darzustellen.

• Ein modifizierter Graph wird generiert, indem bestimmte Q-Eckpunkte aus einer Matrix oder Liste entfernt werden.

• Legen Sie eine Variable fest, um die Anzahl der verbundenen Komponenten zu verfolgen.

• Aktualisiert zunächst jeden Scheitelpunkt im Diagramm iterativ.

• Wenden Sie einen Graph-Traversal-Algorithmus (DFS oder BFS) auf jeden unerforschten Scheitelpunkt an.

• Markieren Sie die während der Durchquerung besuchten Scheitelpunkte, um eine erneute Verarbeitung zu verhindern.

• Fahren Sie weiter, bis alle Scheitelpunkte im Zusammenhang mit dem ursprünglichen Scheitelpunkt gesehen wurden.

• Erhöhen Sie für jeden gefundenen eindeutigen Satz miteinander verbundener Eckpunkte die Anzahl der verbundenen Komponenten in der Gleichung um 1.

• Um auf jeden Scheitelpunkt im aktualisierten Diagramm zuzugreifen, wiederholen Sie die Schritte 5 bis 8 nach Bedarf.

• Nach dem Entfernen der erforderlichen Eckpunkte wird die Gesamtzahl der nicht verbundenen Untergraphen im Diagramm durch den Endwert der Anzahl verbundener Komponenten dargestellt.

Beispiel

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

Ausgabe

Number of nodes accessible from all other nodes: 2

Fazit

Zusammenfassend lässt sich sagen, dass eine Schlüsselmetrik in der Netzwerkanalyse und verwandten Bereichen die Anzahl der verbundenen Komponenten ist, die nach dem Entfernen einer bestimmten Anzahl von Eckpunkten im Diagramm verbleiben. Sowohl matrizenbasierte Methoden als auch der Kosaraju-Algorithmus bieten effiziente Möglichkeiten zur Berechnung dieser Anzahl. Matrixbasierte Methoden verwenden Graph-Traversal-Algorithmen wie DFS oder BFS für den neu gestalteten Graphen, um verknüpfte Komponenten effizient zu finden, während der Kosaraju-Algorithmus die Tiefensuche in zwei Traversierungen verwendet, um stark verbundene Komponenten zu identifizieren. Beide Methoden liefern auch nach dem Entfernen einiger Eckpunkte zuverlässige Ergebnisse und helfen dabei, die Konnektivität und strukturellen Eigenschaften des Diagramms zu verstehen. Die Eigenschaften des Diagramms und die spezifischen Anforderungen der aktuellen Herausforderung bestimmen die zu verwendende Methode.

Das obige ist der detaillierte Inhalt vonDie Anzahl der verbundenen Komponenten eines bestimmten Graphen nach dem Löschen der angegebenen Q-Eckpunkte. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!