Pelaksanaan hipergraf

Dalam tutorial ini, kita akan belajar untuk melaksanakan hipergraf dalam C++.

Definisi- Hipergraf ialah versi khas graf. Satu daripadanya boleh menyambungkan 2 atau lebih bucu.

Dalam graf biasa, satu tepi hanya boleh menyambungkan 2 bucu, tetapi hipergraf ialah generalisasi graf dan boleh digunakan untuk menyambung lebih daripada 2 bucu dengan satu tepi.

Dalam hipergraf, tepi dipanggil hyperedges. Kita boleh mewakili hipergraf dengan H(E, V), di mana E ialah hyperedge dan v ialah set bucu yang disambungkan oleh hyperedge tunggal.

Di sini, kami telah melaksanakan hipergraf.

Contoh

Dalam contoh di bawah, kami menunjukkan pelaksanaan hipergraf menggunakan struktur data peta dalam C++. Dalam peta, kami menyimpan nama tepi sebagai kunci dan set bucu yang disambungkan oleh tepi sebagai nilai.

Selepas itu, kami menggunakan kaedah erase() untuk memadam "edge2" daripada graf. Selain itu, gunakan kaedah insert() untuk memasukkan "edge4" yang menyambungkan 4 bucu ke dalam graf.

Akhir sekali, kami mencetak semua tepi graf dan bucu bersambungnya.

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

Output

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

Kerumitan masa - O(N) untuk merentasi semua tepi.

Kerumitan ruang - O(N) untuk menyimpan N tepi.

Dalam contoh di atas, kita melihat bahawa hyperedges boleh menyambungkan bucu yang berbeza.

Kes penggunaan kehidupan sebenar untuk Hipergraf

Apabila kita melihat pelaksanaan hipergraf berbanding graf biasa, persoalan pertama ialah mengapa kita harus menggunakan hipergraf. Di sini kita akan melihat beberapa kes penggunaan dunia sebenar di mana hipergraf boleh digunakan.

• Rangkaian Sosial- Kita boleh menggunakan hipergraf untuk mewakili rangkaian sosial. Dalam rangkaian sosial, orang mungkin disambungkan kepada perhubungan yang berbeza, seperti persahabatan, rakan sekerja, keluarga, dsb. Oleh itu, kita boleh menggunakan setiap tepi sebagai hubungan dan setiap orang sebagai puncak graf. Sekarang, kita boleh mempertimbangkan bahawa mungkin terdapat lebih daripada dua orang dalam setiap perhubungan. Contohnya, sebuah keluarga yang terdiri daripada 4 hingga 5 orang dan sekumpulan 10 orang rakan.

• Pemodelan Pangkalan Data- Kita boleh menggunakan hipergraf untuk memodelkan pangkalan data di mana kita perlu menyertai berbilang atribut jadual dalam satu perhubungan.

• Perwakilan Sistem Kompleks- Satu lagi kes penggunaan penggunaan hipergraf ialah pembangunan sistem yang kompleks seperti sistem pengangkutan, interaksi biologi, dll.

Jenis hipergraf

Di sini kita akan membincangkan 5 jenis hipergraf.

• Hipergraf seragam: Setiap tepi hipergraf seragam mengandungi bilangan bucu yang sama.

• Hipergraf dwipartit: Dalam hipergraf dwipartit, setiap bucu dibahagikan kepada dua set bercapah. Tambahan pula, setiap hyperedge mengandungi bucu daripada kedua-dua set.

• Hipergraf terarah: Dalam hipergraf terarah, setiap hyperedge mempunyai arah. Oleh itu, kita perlu mempertimbangkan susunan di mana setiap hyperedge menghubungkan bucu.

• Hipergraf Berwajaran: Kami boleh menetapkan pemberat pada setiap sambungan bucu, dengan itu memberikan kepentingan yang berbeza kepada setiap sambungan.

• Hipergraf Berlabel: Kami boleh menambah label pada setiap sambungan bucu untuk menyampaikan lebih banyak maklumat tentang bucu.

Di sini kami telah melaksanakan hipergraf asas. Walau bagaimanapun, dalam pembangunan masa nyata, hyperedge tunggal boleh menyambungkan ratusan bucu graf. Selain itu, kami melihat jenis hipergraf dan kes penggunaan kehidupan sebenar.

Atas ialah kandungan terperinci Pelaksanaan hipergraf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!