Υπεργράφημα

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

Ένα παράδειγμα ενός μη κατευθυνόμενου γραφήματος, με $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\subseteq {\mathcal {P}}(X)\backslash \{\emptyset \}$. Τα στοιχεία του $E$ καλούνται ακμές ή υπερακμές, οπότε γι' αυτό καμιά φορά τα $X$ και $E$ καλούνται σύνολο κορυφών και σύνολο ακμών (ή υπερακμών) αντίστοιχα. Ο πληθάριθμος του συνόλου κορυφών $X$ καλείται τάξη του υπεργραφήματος και ο πληθάριθμος του συνόλου ακμών $E$ καλείται μέγεθος του υπεργραφήματος.

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

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

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

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

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

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

Ένα παράδειγμα ενός κατευθυνόμενου υπεργραφήματος με $X=\{1,2,3,4,5,6\}$ και $E={\big \{}(\{1\},\{2\}),(\{2\},\{3\}),(\{3\},\{1\}),(\{2,3\},\{4,5\}),(\{3,5\},\{6\}){\big \}}$

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

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

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

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

• 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. 
• Πρότυπο:PlanetMath attribution