Υπεργράφημα: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε

Ενδογραμμικά

Έκδοση από την 05:28, 14 Ιουνίου 2022

Στα μαθηματικά, υπεργράφημα είναι μια γενίκευση της έννοιας του γραφήματος, στην οποία μια ακμή μπορεί να συνδέσει οσοδήποτε μεγάλο πλήθος κορυφών. Σε αντιδιαστολή, στα συνήθη γραφήματα κάθε ακμή συνδέει ακριβώς δύο κορυφές (όχι κατ' ανάγκη διακεκριμένες).

Ένα παράδειγμα ενός μη κατευθυνόμενου υπεργραφήματος, με $X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ και $E=\{e_{1},e_{2},e_{3},e_{4}\}={\big \{}\{v_{1},v_{2},v_{3}\},\{v_{2},v_{3}\},\{v_{3},v_{5},v_{6}\},\{v_{4}\}{\big \}}$ Αυτό το υπεργράφημα έχει τάξη επτά και μέγεθος τέσσερα. Παρατηρήστε ότι οι έδρες (οι οποίες αναπαρίστανται με χρωματιστές περιοχές) δεν συνδέουν απλώς δύο κορυφές, αλλά περισσότερες.

Τυπικά, ένα μη κατευθυνόμενο υπεργράφημα $H$ είναι ένα διατεταγμένο ζεύγος $H=(X,E)$ , όπου $X$ είναι ένα σύνολο του οποίου τα στοιχεία ονομάζονται κορυφές, και το $E$ είναι ένα σύνολο μη κενών υποσυνόλων του $X$ , δηλαδή $E\in {\mathcal {P}}(X)\backslash \{\emptyset \}$ . Τα στοιχεία του $E$ καλούνται ακμές ή υπερακμές, οπότε γι' αυτό καμιά φορά τα $X$ και $E$ καλούνται σύνολο κορυφών και σύνολο ακμών (ή υπερακμών) αντίστοιχα. Ο πληθάριθμος του συνόλου κορυφών $X$ καλείται τάξη του υπεργραφήματος και ο πληθάριθμος του συνόλου ακμών $E$ καλείται μέγεθος του υπεργραφήματος.

Τα κατευθυνόμενα υπεργραφήματα διαφέρουν από τα μη κατευθυνόμενα υπεργραφήματα στις ακμές - οι υπερακμές δεν είναι πλέον σύνολα, αλλά διατεταγμένα ζεύγη στοιχείων του $X$ .

Όπως ήδη αναφέρθηκε, οι ακμές των συνήθων γραφημάτων συνδέουν μόνο δύο κορυφές, ενώ οι υπερακμές δεν έχουν κάποιο περιορισμό ως προς το πλήθος των κορυφών που συνδέουν. Παρ' όλα αυτά, συνήθως είναι επιθυμητό να μελετηθούν υπεργραφήματα στα οποία όλες οι υπερακμές συνδέουν το ίδιο πλήθος κορυφών, δηλαδή οι πληθάριθμοι των υπερακμών ισούνται. Τέτοιου είδους γραφήματα όπου για κάθε $e\in E$ αληθεύει $|e|=k$ , ονομάζονται $k-$ ομοιόμορφα υπεργραφήματα. Μ' αυτόν τον ορισμό, ένα $2-$ ομοιόμορφο υπεργράφημα είναι ένα σύνηθες γράφημα, ένα $3-$ ομοιόμορφο υπεργράφημα είναι ένα υπεργράφημα του οποίου οι ακμές συνδέουν τρεις κορυφές κ.ο.κ. Ένα μη κατευθυνόμενο υπεργράφημα καλείται επίσης σύστημα συνόλων ή οικογένεια συνόλων επιλεγόμενη από τον κόσμο αντικειμένων (ο κόσμος με την συνολοθεωρητική έννοια).

Τα υπεργραφήματα μπορούν να ειδωθούν ως δομές πρόσπτωσης. Συγκεκριμένα, υπάρχει ένα διμερές "γράφημα προσπτώσεων" ή αλλιώς "γράφημα Levi" που αντιστοιχεί σε κάθε υπεργράφημα. Κατ' επέκταση, πολλά (αλλά όχι όλα) τα διμερή γραφήματα μπορούν να ειδωθούν ως γραφήματα προσπτώσεων υπεργραφημάτων.

Τα υπεργραφήματα εμφανίζονται συχνά στον χώρο των μαθηματικών, με διάφορες ονομασίες. Στην υπολογιστική γεωμετρία, τα μη κατευθυνόμενα γραφήματα καλούνται range spaces και οι υπερακμές ranges. ^[1] Στην συνεργατική θεωρία παιγνίων, τα υπεργραφήματα ονομάζονται απλά παιχνίδια (παιχνίδια ψήφων) - αυτή η ιδέα χρησιμοποιείται για την επίλυση προβλημάτων στη θεωρία της κοινωνικής επιλογής (social choice theory). Μερικές φορές στη βιβλιογραφία οι ακμές ονομάζονται υπεσύνδεσμοι ή σύνδεσμοι. ^[2]

Η οικογένεια των υπεργραφημάτων είναι μια κατηγορία με μορφισμούς τους ομομορφισμούς των υπεργραφημάτων.

Μία εναλλακτική αναπαράσταση του υπεργραφήματος της προηγούμενης εικόνας, η οποία ονομάζεται αναπαράσταση PAOH.^[3] Οι ακμές είναι οι κατακόρυφες γραμμές που εννώνουν τις κορυφές. Η κορυφή $v_{7}$ είναι, αυτό που λέμε, μεμονωμένη κορυφή. Ο πίνακας στα δεξιά δίνει τα ονόματα των ακμών.

Εφαρμογές

Τα μη κατευθυνόμενα υπεργραφήματα είναι χρήσιμα στη μοντελοποίηση προβλημάτων satisfiability,^[4] στις βάσεις δεδομένων,^[5] στην εκμάθηση μηχανών και στα προβλήματα δένδρων, του Steiner.^[6] Ιδίως στην εκμάθηση μηχανών, τα υπεργραφήματα έχουν χρησιμοποιηθεί ευραίως στην μοντελοποίηση δεδομένων και στην κανονικοποίηση (regularization).^[7] Οι εφαρμογές τους επίσης περιλαμβάνουν τα recommender systems (οι κοινότητες αναπαρίστανται ως υπερακμές),^[8] στο image retrieval (οι εξαρτήσεις αναπαρίστανται ως υπερακμές),^[9] και στα bioinformatics (οι βιοχημικές αλληλεπιδράσεις αναπαρίστανται ως υπερακμές).^[10] Αντιπροσωπευτικές τεχνικές εκμάθησης με υπεργραφήματα περιλαμβάνουν το spectral clustering των υπεργραφημάτων (το οποίο επεκτείνει την spectral γραφοθεωρία με Laplacianές υπεργραφημάτων)^[11] και το semi-supervised learning των υπεργραφημάτων (το οποίο εισάγει επιπλέον κόστος στη δομή του υπεργραφήματος, για να περιορίσει τα αποτελέσματα της εκμάθησης).^[12] Για μεγάλα υπεργραφήματα, είναι διαθέσιμο ένα distributed framework build,^[13] το οποίο χρησιμοποιεί το Apache Spark.

Τα κατευθυνόμενα υπεργραφήματα μπορούν να χρησιμοποιηθούν στην μοντελοποίηση, για παράδειγμα στην τηλεφωνία,^[14] στην ανίχνευση ξεπλήματος χρήματος,^[15] στο operation research,^[16] και στον προγραμματισμό των μεταφορών. Είναι επίσης δυνατόν να μοντελοποιήσουν την Horn-satisfiability.^[17]

(Εκκρεμμεί η μετάφραση)

Γενικεύσεις εννοιών από τα συνήθη γραφήματα

Πολλά θεωρήματα και έννοιες των απλών γραφημάτων μεταβιβάζονται σχεδόν αυτούσια στα υπεργραφήματα. Συγκεκριμένα, στα μη κατευθυνόμενα υπεργραφήματα:

Το ταίριασμα στα υπεργραφήματα,
Τα καλύμματα κορυφών στα υπεργραφήματα,
Ο γραμμογράφος (line graph) ενός υπεργραφήματος,
Η γραμματική των υπεργραφημάτων,
Το θεώρημα του Ramsey,
Το θεώρημα Erdős–Ko–Rado,
Το θεώρημα Kruskai-Katona, στα ομοιόμορφα υπεργραφήματα,
Θεωρήματα τύπου Hall για υπεργραφήματα.

Στα κατευθυνόμενα υπεργραφήματα: η μεταβατική κλειστότητα, και τα προβλήματα εύρεσης συντομότερου μονοπατιού.^[18]

Αναπαραστάσεις υπεργραφημάτων

Χρωματισμοί υπεργραφημάτων

Ιδιότητες των υπεργραφημάτων

Σχετικά υπεργραφήματα

Πίνακες πρόσπτωσης

Ξενόγλωσσες σελίδες του ίδιου λήμματος

Το παρόν λήμμα αποτελεί μετάφραση του αντίστοιχου αγγλικού: hypergraph.

Παραπομπές

↑ Haussler, David; Welzl, Emo (1987-06-01). «ɛ-nets and simplex range queries» (στα αγγλικά). Discrete & Computational Geometry 2 (2): 127–151. doi:10.1007/BF02187876. ISSN 1432-0444. https://doi.org/10.1007/BF02187876.
↑ Pearl, Judea (1984). Heuristics : intelligent search strategies for computer problem solving. Reading, Mass.: Addison-Wesley Pub. Co. ISBN 0-201-05594-5. 9644728.
↑ Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2021-01-01). «Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization». IEEE Transactions on Visualization and Computer Graphics 27 (1): 1–13. doi:10.1109/TVCG.2019.2933196. ISSN 1077-2626. https://ieeexplore.ieee.org/document/8789484/.
↑ Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006-10). «Witnesses for non-satisfiability of dense random 3CNF formulas». 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06): 497–508. doi:10.1109/FOCS.2006.78. https://ieeexplore.ieee.org/document/4031385/.
↑ Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015-11). «Scalable Hypergraph Learning and Processing». 2015 IEEE International Conference on Data Mining (Atlantic City, NJ, USA: IEEE): 775–780. doi:10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. http://ieeexplore.ieee.org/document/7373388/.
↑ Brazil, Marcus· Zachariasen, Martin (2015). Steiner Trees in Graphs and Hypergraphs. 29. Cham: Springer International Publishing. σελίδες 301–317. ISBN 978-3-319-13914-2.
↑ Schölkopf, Bernhard· Platt, John C. (2007). Advances in neural information processing systems 19 : proceedings of the 2006 conference. Cambridge, Mass.: MIT Press. ISBN 978-0-262-25691-9. 648314857.
↑ Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (2011-10). «Using rich social media information for music recommendation via hypergraph model» (στα αγγλικά). ACM Transactions on Multimedia Computing, Communications, and Applications 7S (1): 1–22. doi:10.1145/2037676.2037679. ISSN 1551-6857. https://dl.acm.org/doi/10.1145/2037676.2037679.
↑ Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2011-10). «Hypergraph with sampling for image retrieval» (στα αγγλικά). Pattern Recognition 44 (10-11): 2255–2262. doi:10.1016/j.patcog.2010.07.014. https://linkinghub.elsevier.com/retrieve/pii/S0031320310003535.
↑ Patro, Rob; Kingsford, Carl (2013-07). «Predicting protein interactions via parsimonious network history inference» (στα αγγλικά). Bioinformatics 29 (13): i237–i246. doi:10.1093/bioinformatics/btt224. ISSN 1367-4803. PMID 23812989. PMC PMC3694678. https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btt224.
↑ Yue Gao; Meng Wang; Zheng-Jun Zha; Jialie Shen; Xuelong Li; Xindong Wu (2013-01). «Visual-Textual Joint Relevance Learning for Tag-Based Social Image Search». IEEE Transactions on Image Processing 22 (1): 363–376. doi:10.1109/TIP.2012.2202676. ISSN 1057-7149. http://ieeexplore.ieee.org/document/6212356/.
↑ Tian, Z.; Hwang, T.; Kuang, R. (2009-11-01). «A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge» (στα αγγλικά). Bioinformatics 25 (21): 2831–2838. doi:10.1093/bioinformatics/btp467. ISSN 1367-4803. https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btp467.
↑ Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015-11). «Scalable Hypergraph Learning and Processing». 2015 IEEE International Conference on Data Mining (Atlantic City, NJ, USA: IEEE): 775–780. doi:10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. http://ieeexplore.ieee.org/document/7373388/.
↑ Goldstein, A. J. (1982-11). «Database Systems : A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant» (στα αγγλικά). Bell System Technical Journal 61 (9): 2529–2554. doi:10.1002/j.1538-7305.1982.tb03439.x. https://ieeexplore.ieee.org/document/6772070.
↑ Ranshous, Stephen· Joslyn, Cliff A. (2017). Brenner, Michael, επιμ. Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph. 10323. Cham: Springer International Publishing. σελίδες 248–263. ISBN 978-3-319-70277-3.
↑ Ausiello, Giorgio; Laura, Luigi (2017-01). «Directed hypergraphs: Introduction and fundamental algorithms—A survey» (στα αγγλικά). Theoretical Computer Science 658: 293–306. doi:10.1016/j.tcs.2016.03.016. https://linkinghub.elsevier.com/retrieve/pii/S0304397516002097.
↑ Gallo, Giorgio; Longo, Giustino; Pallottino, Stefano; Nguyen, Sang (1993-04). «Directed hypergraphs and applications» (στα αγγλικά). Discrete Applied Mathematics 42 (2-3): 177–201. doi:10.1016/0166-218X(93)90045-P. https://linkinghub.elsevier.com/retrieve/pii/0166218X9390045P.
↑ Ausiello, Giorgio; Laura, Luigi (2017-01). «Directed hypergraphs: Introduction and fundamental algorithms—A survey» (στα αγγλικά). Theoretical Computer Science 658: 293–306. doi:10.1016/j.tcs.2016.03.016. https://linkinghub.elsevier.com/retrieve/pii/S0304397516002097.

Βιβλιογραφία

Berge, Claude (1984). Hypergraphs: Combinatorics of Finite Sets. Elsevier. ISBN 978-0-08-088023-5.
Berge, C.· Ray-Chaudhuri, D. (2006). Hypergraph Seminar: Ohio State University, 1972. Lecture Notes in Mathematics. 411. Springer. ISBN 978-3-540-37803-7.
Hazewinkel, Michiel, επιμ.. (2001), «Hypergraph», Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://www.encyclopediaofmath.org/index.php?title=p/h048470
Bretto, Alain (2013). Hypergraph Theory: An Introduction. Springer. ISBN 978-3-319-00080-0.
Voloshin, Vitaly I. (2002). Coloring Mixed Hypergraphs: Theory, Algorithms and Applications: Theory, Algorithms, and Applications. Fields Institute Monographs. 17. American Mathematical Society. ISBN 978-0-8218-2812-0.
Voloshin, Vitaly I. (2009). Introduction to Graph and Hypergraph Theory. Nova Science. ISBN 978-1-61470-112-5.

[1] Haussler, David; Welzl, Emo (1987-06-01). «ɛ-nets and simplex range queries» (στα αγγλικά). Discrete & Computational Geometry 2 (2): 127–151. doi:10.1007/BF02187876. ISSN 1432-0444. https://doi.org/10.1007/BF02187876.

[2] Pearl, Judea (1984). Heuristics : intelligent search strategies for computer problem solving. Reading, Mass.: Addison-Wesley Pub. Co. ISBN 0-201-05594-5. 9644728.

[3] Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2021-01-01). «Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization». IEEE Transactions on Visualization and Computer Graphics 27 (1): 1–13. doi:10.1109/TVCG.2019.2933196. ISSN 1077-2626. https://ieeexplore.ieee.org/document/8789484/.

[4] Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006-10). «Witnesses for non-satisfiability of dense random 3CNF formulas». 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06): 497–508. doi:10.1109/FOCS.2006.78. https://ieeexplore.ieee.org/document/4031385/.

[5] Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015-11). «Scalable Hypergraph Learning and Processing». 2015 IEEE International Conference on Data Mining (Atlantic City, NJ, USA: IEEE): 775–780. doi:10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. http://ieeexplore.ieee.org/document/7373388/.

[6] Brazil, Marcus· Zachariasen, Martin (2015). Steiner Trees in Graphs and Hypergraphs. 29. Cham: Springer International Publishing. σελίδες 301–317. ISBN 978-3-319-13914-2.

[7] Schölkopf, Bernhard· Platt, John C. (2007). Advances in neural information processing systems 19 : proceedings of the 2006 conference. Cambridge, Mass.: MIT Press. ISBN 978-0-262-25691-9. 648314857.

[8] Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (2011-10). «Using rich social media information for music recommendation via hypergraph model» (στα αγγλικά). ACM Transactions on Multimedia Computing, Communications, and Applications 7S (1): 1–22. doi:10.1145/2037676.2037679. ISSN 1551-6857. https://dl.acm.org/doi/10.1145/2037676.2037679.

[9] Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2011-10). «Hypergraph with sampling for image retrieval» (στα αγγλικά). Pattern Recognition 44 (10-11): 2255–2262. doi:10.1016/j.patcog.2010.07.014. https://linkinghub.elsevier.com/retrieve/pii/S0031320310003535.

[10] Patro, Rob; Kingsford, Carl (2013-07). «Predicting protein interactions via parsimonious network history inference» (στα αγγλικά). Bioinformatics 29 (13): i237–i246. doi:10.1093/bioinformatics/btt224. ISSN 1367-4803. PMID 23812989. PMC PMC3694678. https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btt224.

[11] Yue Gao; Meng Wang; Zheng-Jun Zha; Jialie Shen; Xuelong Li; Xindong Wu (2013-01). «Visual-Textual Joint Relevance Learning for Tag-Based Social Image Search». IEEE Transactions on Image Processing 22 (1): 363–376. doi:10.1109/TIP.2012.2202676. ISSN 1057-7149. http://ieeexplore.ieee.org/document/6212356/.

[12] Tian, Z.; Hwang, T.; Kuang, R. (2009-11-01). «A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge» (στα αγγλικά). Bioinformatics 25 (21): 2831–2838. doi:10.1093/bioinformatics/btp467. ISSN 1367-4803. https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btp467.

[13] Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015-11). «Scalable Hypergraph Learning and Processing». 2015 IEEE International Conference on Data Mining (Atlantic City, NJ, USA: IEEE): 775–780. doi:10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. http://ieeexplore.ieee.org/document/7373388/.

[14] Goldstein, A. J. (1982-11). «Database Systems : A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant» (στα αγγλικά). Bell System Technical Journal 61 (9): 2529–2554. doi:10.1002/j.1538-7305.1982.tb03439.x. https://ieeexplore.ieee.org/document/6772070.

[15] Ranshous, Stephen· Joslyn, Cliff A. (2017). Brenner, Michael, επιμ. Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph. 10323. Cham: Springer International Publishing. σελίδες 248–263. ISBN 978-3-319-70277-3.

[16] Ausiello, Giorgio; Laura, Luigi (2017-01). «Directed hypergraphs: Introduction and fundamental algorithms—A survey» (στα αγγλικά). Theoretical Computer Science 658: 293–306. doi:10.1016/j.tcs.2016.03.016. https://linkinghub.elsevier.com/retrieve/pii/S0304397516002097.

[17] Gallo, Giorgio; Longo, Giustino; Pallottino, Stefano; Nguyen, Sang (1993-04). «Directed hypergraphs and applications» (στα αγγλικά). Discrete Applied Mathematics 42 (2-3): 177–201. doi:10.1016/0166-218X(93)90045-P. https://linkinghub.elsevier.com/retrieve/pii/0166218X9390045P.

[18] Ausiello, Giorgio; Laura, Luigi (2017-01). «Directed hypergraphs: Introduction and fundamental algorithms—A survey» (στα αγγλικά). Theoretical Computer Science 658: 293–306. doi:10.1016/j.tcs.2016.03.016. https://linkinghub.elsevier.com/retrieve/pii/S0304397516002097.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

@@ Γραμμή 16: / Γραμμή 16: @@
 [[Αρχείο:PAOH hypergraph representation.png|καθόλου|με-πλαίσιο|Μία εναλλακτική αναπαράσταση του υπεργραφήματος της προηγούμενης εικόνας, η οποία ονομάζεται αναπαράσταση PAOH.<ref>{{Cite journal|title=Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization|url=https://ieeexplore.ieee.org/document/8789484/|journal=IEEE Transactions on Visualization and Computer Graphics|date=2021-01-01|issn=1077-2626|pages=1–13|volume=27|issue=1|doi=10.1109/TVCG.2019.2933196|first=Paola|last=Valdivia|first2=Paolo|last2=Buono|first3=Catherine|last3=Plaisant|first4=Nicole|last4=Dufournaud|first5=Jean-Daniel|last5=Fekete}}</ref> Οι ακμές είναι οι κατακόρυφες γραμμές που εννώνουν τις κορυφές. Η κορυφή <math>v_7</math> είναι, αυτό που λέμε, μεμονωμένη κορυφή. Ο πίνακας στα δεξιά δίνει τα ονόματα των ακμών. ]]
 [[Αρχείο:Directed hypergraph example.svg|καθόλου|μικρογραφία|438x438px|Ένα παράδειγμα ενός κατευθυνόμενου υπεργραφήματος με <math>X = \{1,2,3,4,5,6\}</math> και <math>E = \big\{ (\{1\}, \{2\}), (\{2\}, \{3\}), (\{3\}, \{1\}), (\{2,3\}, \{4,5\}), (\{3,5\}, \{6\}) \big\}</math>]]
-'''''(Εκκρεμμεί η μετάφραση)'''''
 == Εφαρμογές ==
+Τα μη κατευθυνόμενα υπεργραφήματα είναι χρήσιμα στη μοντελοποίηση προβλημάτων satisfiability,<ref>{{Cite journal|title=Witnesses for non-satisfiability of dense random 3CNF formulas|url=https://ieeexplore.ieee.org/document/4031385/|journal=2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)|date=2006-10|pages=497–508|doi=10.1109/FOCS.2006.78|first=Uriel|last=Feige|first2=Jeong Han|last2=Kim|first3=Eran|last3=Ofek}}</ref> στις [[Βάση δεδομένων|βάσεις δεδομένων]],<ref>{{Cite journal|title=Scalable Hypergraph Learning and Processing|url=http://ieeexplore.ieee.org/document/7373388/|publisher=IEEE|journal=2015 IEEE International Conference on Data Mining|date=2015-11|location=Atlantic City, NJ, USA|isbn=978-1-4673-9504-5|pages=775–780|doi=10.1109/ICDM.2015.33|first=Jin|last=Huang|first2=Rui|last2=Zhang|first3=Jeffrey Xu|last3=Yu}}</ref> στην εκμάθηση μηχανών και στα [[προβλήματα δένδρων, του Steiner]].<ref>{{Cite book|title=Steiner Trees in Graphs and Hypergraphs|first=Marcus|last=Brazil|first2=Martin|last2=Zachariasen|publisher=Springer International Publishing|isbn=978-3-319-13914-2|date=2015|volume=29|location=Cham|pages=301–317|url=http://link.springer.com/10.1007/978-3-319-13915-9_5}}</ref> Ιδίως στην εκμάθηση μηχανών, τα υπεργραφήματα έχουν χρησιμοποιηθεί ευραίως στην μοντελοποίηση δεδομένων και στην [[Κανονικοποίηση (μαθηματικά)|κανονικοποίηση]] (regularization).<ref>{{Cite book|title=Advances in neural information processing systems 19 : proceedings of the 2006 conference|first=Bernhard|last=Schölkopf|first2=John C.|last2=Platt|publisher=MIT Press|isbn=978-0-262-25691-9|date=2007|location=Cambridge, Mass.|url=https://www.worldcat.org/oclc/648314857|id=648314857}}</ref> Οι εφαρμογές τους επίσης περιλαμβάνουν τα recommender systems (οι κοινότητες αναπαρίστανται ως υπερακμές),<ref>{{Cite journal|title=Using rich social media information for music recommendation via hypergraph model|url=https://dl.acm.org/doi/10.1145/2037676.2037679|journal=ACM Transactions on Multimedia Computing, Communications, and Applications|date=2011-10|issn=1551-6857|pages=1–22|volume=7S|issue=1|doi=10.1145/2037676.2037679|language=en|first=Shulong|last=Tan|first2=Jiajun|last2=Bu|first3=Chun|last3=Chen|first4=Bin|last4=Xu|first5=Can|last5=Wang|first6=Xiaofei|last6=He}}</ref> στο image retrieval (οι εξαρτήσεις αναπαρίστανται ως υπερακμές),<ref>{{Cite journal|title=Hypergraph with sampling for image retrieval|url=https://linkinghub.elsevier.com/retrieve/pii/S0031320310003535|journal=Pattern Recognition|date=2011-10|pages=2255–2262|volume=44|issue=10-11|doi=10.1016/j.patcog.2010.07.014|language=en|first=Qingshan|last=Liu|first2=Yuchi|last2=Huang|first3=Dimitris N.|last3=Metaxas}}</ref> και στα bioinformatics (οι βιοχημικές αλληλεπιδράσεις αναπαρίστανται ως υπερακμές).<ref>{{Cite journal|title=Predicting protein interactions via parsimonious network history inference|url=https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btt224|journal=Bioinformatics|date=2013-07|issn=1367-4803|pmc=PMC3694678|pmid=23812989|pages=i237–i246|volume=29|issue=13|doi=10.1093/bioinformatics/btt224|language=en|first=Rob|last=Patro|first2=Carl|last2=Kingsford}}</ref> Αντιπροσωπευτικές τεχνικές εκμάθησης με υπεργραφήματα περιλαμβάνουν το spectral clustering των υπεργραφημάτων (το οποίο επεκτείνει την spectral γραφοθεωρία με Laplacianές υπεργραφημάτων)<ref>{{Cite journal|title=Visual-Textual Joint Relevance Learning for Tag-Based Social Image Search|url=http://ieeexplore.ieee.org/document/6212356/|journal=IEEE Transactions on Image Processing|date=2013-01|issn=1057-7149|pages=363–376|volume=22|issue=1|doi=10.1109/TIP.2012.2202676|last=Yue Gao|last2=Meng Wang|last3=Zheng-Jun Zha|last4=Jialie Shen|last5=Xuelong Li|last6=Xindong Wu}}</ref> και το semi-supervised learning των υπεργραφημάτων (το οποίο εισάγει επιπλέον κόστος στη δομή του υπεργραφήματος, για να περιορίσει τα αποτελέσματα της εκμάθησης).<ref>{{Cite journal|title=A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge|url=https://academic.oup.com/bioinformatics/article-lookup/doi/10.1093/bioinformatics/btp467|journal=Bioinformatics|date=2009-11-01|issn=1367-4803|pages=2831–2838|volume=25|issue=21|doi=10.1093/bioinformatics/btp467|language=en|first=Z.|last=Tian|first2=T.|last2=Hwang|first3=R.|last3=Kuang}}</ref> Για μεγάλα υπεργραφήματα, είναι διαθέσιμο ένα distributed framework build,<ref>{{Cite journal|title=Scalable Hypergraph Learning and Processing|url=http://ieeexplore.ieee.org/document/7373388/|publisher=IEEE|journal=2015 IEEE International Conference on Data Mining|date=2015-11|location=Atlantic City, NJ, USA|isbn=978-1-4673-9504-5|pages=775–780|doi=10.1109/ICDM.2015.33|first=Jin|last=Huang|first2=Rui|last2=Zhang|first3=Jeffrey Xu|last3=Yu}}</ref> το οποίο χρησιμοποιεί το [[Apache Spark]].
+Τα κατευθυνόμενα υπεργραφήματα μπορούν να χρησιμοποιηθούν στην μοντελοποίηση, για παράδειγμα στην [[τηλεφωνία]],<ref>{{Cite journal|title=Database Systems : A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant|url=https://ieeexplore.ieee.org/document/6772070|journal=Bell System Technical Journal|date=1982-11|pages=2529–2554|volume=61|issue=9|doi=10.1002/j.1538-7305.1982.tb03439.x|language=en|first=A. J.|last=Goldstein}}</ref> στην ανίχνευση [[Ξέπλυμα μαύρου χρήματος|ξεπλήματος χρήματος]],<ref>{{Cite book|title=Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph|first=Stephen|last=Ranshous|first2=Cliff A.|last2=Joslyn|publisher=Springer International Publishing|isbn=978-3-319-70277-3|date=2017|editor-last=Brenner|editor-first=Michael|volume=10323|location=Cham|pages=248–263|url=http://link.springer.com/10.1007/978-3-319-70278-0_16}}</ref> στο operation research,<ref>{{Cite journal|title=Directed hypergraphs: Introduction and fundamental algorithms—A survey|url=https://linkinghub.elsevier.com/retrieve/pii/S0304397516002097|journal=Theoretical Computer Science|date=2017-01|pages=293–306|volume=658|doi=10.1016/j.tcs.2016.03.016|language=en|first=Giorgio|last=Ausiello|first2=Luigi|last2=Laura}}</ref> και στον προγραμματισμό των μεταφορών. Είναι επίσης δυνατόν να μοντελοποιήσουν την Horn-satisfiability.<ref>{{Cite journal|title=Directed hypergraphs and applications|url=https://linkinghub.elsevier.com/retrieve/pii/0166218X9390045P|journal=Discrete Applied Mathematics|date=1993-04|pages=177–201|volume=42|issue=2-3|doi=10.1016/0166-218X(93)90045-P|language=en|first=Giorgio|last=Gallo|first2=Giustino|last2=Longo|first3=Stefano|last3=Pallottino|first4=Sang|last4=Nguyen}}</ref>
+'''''(Εκκρεμμεί η μετάφραση)'''''
 == Γενικεύσεις εννοιών από τα συνήθη γραφήματα ==
+Πολλά [[Θεώρημα|θεωρήματα]] και έννοιες των απλών γραφημάτων μεταβιβάζονται σχεδόν αυτούσια στα υπεργραφήματα. Συγκεκριμένα, στα μη κατευθυνόμενα υπεργραφήματα:
+* Το ταίριασμα στα υπεργραφήματα,
+* Τα καλύμματα κορυφών στα υπεργραφήματα,
+* Ο γραμμογράφος (line graph) ενός υπεργραφήματος,
+* Η γραμματική των υπεργραφημάτων,
+* Το [[θεώρημα του Ramsey]],
+* Το [[θεώρημα Erdős–Ko–Rado]],
+* Το [[θεώρημα Kruskai-Katona]], στα ομοιόμορφα υπεργραφήματα,
+* [[Θεωρήματα τύπου Hall]] για υπεργραφήματα.
+Στα κατευθυνόμενα υπεργραφήματα: η μεταβατική κλειστότητα, και τα προβλήματα εύρεσης συντομότερου μονοπατιού.<ref>{{Cite journal|title=Directed hypergraphs: Introduction and fundamental algorithms—A survey|url=https://linkinghub.elsevier.com/retrieve/pii/S0304397516002097|journal=Theoretical Computer Science|date=2017-01|pages=293–306|volume=658|doi=10.1016/j.tcs.2016.03.016|language=en|first=Giorgio|last=Ausiello|first2=Luigi|last2=Laura}}</ref>
 == Αναπαραστάσεις υπεργραφημάτων ==