Implémentation de l'hypergraphe

Dans ce tutoriel, nous apprendrons à implémenter un hypergraphe en C++.

Définition- Un hypergraphe est une version spéciale d'un graphique. Un seul d’entre eux peut relier 2 sommets ou plus.

Dans un graphe normal, une seule arête ne peut connecter que 2 sommets, mais un hypergraphe est une généralisation du graphe et peut être utilisé pour connecter plus de 2 sommets avec une seule arête.

Dans un hypergraphe, les arêtes sont appelées hyperarêtes. Nous pouvons représenter un hypergraphe par H(E, V), où E est un hyperarête et v est un ensemble de sommets reliés par un seul hyperarête.

Ici, nous avons implémenté un hypergraphe.

Exemple

Dans l'exemple ci-dessous, nous démontrons l'implémentation d'un hypergraphe utilisant la structure de données cartographiques en C++. Dans une carte, nous stockons les noms d'arêtes sous forme de clés et l'ensemble des sommets connectés par les arêtes sous forme de valeurs.

Après cela, nous utilisons la méthode Eraser() pour supprimer "edge2" du graphique. De plus, utilisez la méthode insert() pour insérer "edge4" reliant 4 sommets dans le graphique.

Enfin, nous imprimons toutes les arêtes du graphe et leurs sommets connectés.

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

Sortie

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

Complexité temporelle - O(N) pour parcourir toutes les arêtes.

Complexité spatiale - O(N) pour stocker N arêtes.

Dans l'exemple ci-dessus, nous voyons que les hyperedges peuvent connecter différents sommets.

Cas d'utilisation réels d'Hypergraph

Lorsque nous examinons l'implémentation d'hypergraphes sur des graphiques ordinaires, la première question est de savoir pourquoi nous devrions utiliser des hypergraphes. Nous verrons ici quelques cas d'utilisation réels dans lesquels des hypergraphes peuvent être utilisés.

• Réseaux Sociaux- Nous pouvons utiliser des hypergraphes pour représenter les réseaux sociaux. Dans les réseaux sociaux, les gens peuvent être connectés à différentes relations, comme les amitiés, les collègues, la famille, etc. Par conséquent, nous pouvons utiliser chaque arête comme relation et chaque personne comme sommet du graphique. Or, on peut considérer qu’il peut y avoir plus de deux personnes dans chaque relation. Par exemple, une famille de 4 à 5 personnes et un groupe de 10 amis.

• Modélisation de base de données- Nous pouvons utiliser l'hypergraphe pour modéliser une base de données dans laquelle nous devons joindre plusieurs attributs d'une table dans une seule relation.

• Représentation de systèmes complexes- Un autre cas d'utilisation de l'utilisation d'hypergraphes est le développement de systèmes complexes tels que les systèmes de transport, les interactions biologiques, etc.

Types d'hypergraphes

Ici, nous discuterons de 5 types d'hypergraphes.

• Hypergraphe uniforme : chaque arête d'un hypergraphe uniforme contient le même nombre de sommets.

• Hypergraphe biparti : Dans un hypergraphe biparti, chaque sommet est divisé en deux ensembles disjoints. De plus, chaque hyperedge contient des sommets des deux ensembles.

• Hypergraphe dirigé : Dans un hypergraphe dirigé, chaque hyperbord a une direction. Par conséquent, nous devons considérer l’ordre dans lequel chaque hyperarête connecte les sommets.

• Hypergraphe pondéré : nous pouvons attribuer un poids à chaque connexion de sommet, attribuant ainsi une importance différente à chaque connexion.

• Hypergraphe étiqueté : nous pouvons ajouter des étiquettes à chaque connexion de sommets pour transmettre plus d'informations sur les sommets.

Ici, nous avons implémenté un hypergraphe de base. Cependant, dans le développement en temps réel, un seul hyperedge peut connecter des centaines de sommets de graphe. De plus, nous avons vu des types d’hypergraphes et des cas d’utilisation réels.

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!