Implementierung von Hypergraph

In diesem Tutorial lernen wir, einen Hypergraphen in C++ zu implementieren.

Definition- Ein Hypergraph ist eine spezielle Version eines Graphen. Ein einzelner von ihnen kann zwei oder mehr Eckpunkte verbinden.

In einem normalen Diagramm kann eine einzelne Kante nur zwei Eckpunkte verbinden, aber ein Hypergraph ist eine Verallgemeinerung des Diagramms und kann verwendet werden, um mehr als zwei Eckpunkte mit einer einzelnen Kante zu verbinden.

In einem Hypergraphen werden Kanten Hyperkanten genannt. Wir können einen Hypergraphen durch H(E, V) darstellen, wobei E eine Hyperkante und v eine Menge von Eckpunkten ist, die durch eine einzelne Hyperkante verbunden sind.

Hier haben wir einen Hypergraphen implementiert.

Beispiel

Im folgenden Beispiel demonstrieren wir die Implementierung eines Hypergraphen mithilfe der Kartendatenstruktur in C++. In einer Karte speichern wir Kantennamen als Schlüssel und die Menge der durch die Kanten verbundenen Scheitelpunkte als Werte.

Danach verwenden wir die Methode erase(), um „edge2“ aus dem Diagramm zu löschen. Verwenden Sie außerdem die Methode insert(), um „edge4“ einzufügen, das vier Eckpunkte in das Diagramm verbindet.

Abschließend drucken wir alle Kanten des Diagramms und die damit verbundenen Eckpunkte aus.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

void createHyperGraph() {
    // Creating the hypergraph
    map<string, vector<int>> h_graph = {{"edge1", {32, 21, 90}},
                                        {"edge2", {21, 47, 54}},
                                        {"edge3", {43, 76}}};
    // Removing edge from the hypergraph
    h_graph.erase("edge2");
    // Inserting a new edge in the hypergraph
    h_graph.insert({"edge4", {48, 61, 93, 52, 89}});
    cout << "The hypergraph is :-" << endl;
    for (auto ele : h_graph) {
        string edge = ele.first;
        cout << edge << " : ";
        vector<int> vert = ele.second;
        for (int v : vert) {
            cout << v << " ";
        }
        cout << endl;
    }
}
int main() {
    createHyperGraph();
    return 0;
}

Ausgabe

The hypergraph is :-
edge1 : 32 21 90 
edge3 : 43 76 
edge4 : 48 61 93 52 89

Zeitkomplexität – O(N) zum Durchlaufen aller Kanten.

Raumkomplexität – O(N) zum Speichern von N Kanten.

Im obigen Beispiel sehen wir, dass Hyperkanten verschiedene Eckpunkte verbinden können.

Reale Anwendungsfälle für Hypergraph

Wenn wir uns die Implementierung von Hypergraphen gegenüber gewöhnlichen Graphen ansehen, stellt sich zunächst die Frage, warum wir Hypergraphen verwenden sollten. Hier sehen wir einige reale Anwendungsfälle, in denen Hypergraphen verwendet werden können.

• Soziale Netzwerke- Wir können Hypergraphen verwenden, um soziale Netzwerke darzustellen. In sozialen Netzwerken können Menschen mit unterschiedlichen Beziehungen wie Freundschaften, Kollegen, Familie usw. verbunden sein. Daher können wir jede Kante als Beziehung und jede Person als Scheitelpunkt des Diagramms verwenden. Nun können wir davon ausgehen, dass es in jeder Beziehung mehr als zwei Personen geben kann. Zum Beispiel eine Familie mit 4 bis 5 Personen und eine Gruppe mit 10 Freunden.

• Datenbankmodellierung – Wir können Hypergraph verwenden, um eine Datenbank zu modellieren, in der wir mehrere Attribute einer Tabelle in einer einzigen Beziehung verbinden müssen.

• Komplexe Systemdarstellung – Ein weiterer Anwendungsfall der Verwendung von Hypergraphen ist die Entwicklung komplexer Systeme wie Transportsysteme, biologische Interaktionen usw.

Arten von Hypergraphen

Hier besprechen wir 5 Arten von Hypergraphen.

• Einheitlicher Hypergraph: Jede Kante eines einheitlichen Hypergraphen enthält die gleiche Anzahl von Eckpunkten.

• Bipartiter Hypergraph: In einem bipartiten Hypergraphen ist jeder Scheitelpunkt in zwei disjunkte Mengen unterteilt. Darüber hinaus enthält jede Hyperkante Eckpunkte aus beiden Mengen.

• Gerichteter Hypergraph: In einem gerichteten Hypergraphen hat jede Hyperkante eine Richtung. Daher müssen wir die Reihenfolge berücksichtigen, in der jede Hyperkante Eckpunkte verbindet.

• Gewichteter Hypergraph: Wir können jeder Scheitelpunktverbindung eine Gewichtung zuweisen und so jeder Verbindung eine unterschiedliche Bedeutung zuweisen.

• Beschrifteter Hypergraph: Wir können jeder Verbindung von Scheitelpunkten Beschriftungen hinzufügen, um mehr Informationen über die Scheitelpunkte zu übermitteln.

Hier haben wir einen einfachen Hypergraphen implementiert. In der Echtzeitentwicklung kann ein einzelner Hyperedge jedoch Hunderte von Graphscheitelpunkten verbinden. Darüber hinaus haben wir Arten von Hypergraphen und reale Anwendungsfälle gesehen.

Das obige ist der detaillierte Inhalt vonImplementierung von Hypergraph. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!