Ισομορφισμός (θεωρία γράφων)

Στη θεωρία γράφων, ένας ισομορφισμός γραφημάτων G και H είναι μια αμφίρριψη μεταξύ των συνόλων κορυφών των G και H

έτσι ώστε οποιεσδήποτε δύο κορυφές u και v του G να είναι παρακείμενες στο G αν και μόνο αν οι  και  είναι παρακείμενες στο H. Αυτό το είδος της αμφίρριψης περιγράφεται συνήθως ως "αμφίρριψη που διατηρεί τη δομή", σύμφωνα με τη γενική έννοια του ισομορφισμού που είναι μια structure-preserving bijection.

Αν υπάρχει ισομορφισμός μεταξύ δύο γραφημάτων, τότε τα γραφήματα ονομάζονται ισομορφικά συχνά συμβολιζόμενα με . Στην περίπτωση που ο ισομορφισμός είναι μια απεικόνιση ενός γράφου πάνω στον εαυτό του, δηλαδή όταν τα G και H είναι ένας και ο ίδιος γράφος, ο ισομορφισμός ονομάζεται αυτομορφισμός του G.

Ο ισομορφισμός γράφων είναι μια σχέση ισοδυναμίας σε γράφους και ως τέτοια χωρίζει την κλάση όλων των γράφων σε κλάσεις ισοδυναμίας. Ένα σύνολο ισομορφικών μεταξύ τους γραφημάτων ονομάζεται κλάση ισομορφισμού  γραφημάτων. Το ερώτημα αν ο ισομορφισμός γράφων μπορεί να προσδιοριστεί σε πολυωνυμικό χρόνο είναι ένα σημαντικό άλυτο πρόβλημα της επιστήμης των υπολογιστών, γνωστό ως πρόβλημα ισομορφισμού γράφων.

Οι δύο γράφοι που παρουσιάζονται παρακάτω είναι ισόμορφοι, παρά τα διαφορετικά σχέδια που παρουσιάζουν.

 Γράφος G Γράφος H Ο ισομορφισμόςμεταξύ των G και Hclass=skin-invert|100pxclass=skin-invert|210pxf(a) = 1

f(b) = 6

f(c) = 8

f(d) = 3

f(g) = 5

f(h) = 2

f(i) = 4

f(j) = 7

Μεταβολές

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

Ισομορφισμός γράφων με ετικέτες
Για γράφους με ετικέτες χρησιμοποιούνται δύο ορισμοί του ισομορφισμού.

Σύμφωνα με τον έναν ορισμό, ένας ισομορφισμός είναι μια αμφίρριψη κορυφών που διατηρεί τόσο τις ακμές όσο και τις ετικέτες.p.424

Σύμφωνα με έναν άλλο ορισμό, ένας ισομορφισμός είναι μια αμφίρριψη κορυφών που διατηρεί τις ακμές και διατηρεί κλάσεις ισοδυναμίας των ετικετών, δηλαδή οι κορυφές με ισοδύναμες (π.χ. ίδιες) ετικέτες αντιστοιχίζονται στις κορυφές με ισοδύναμες ετικέτες και αντίστροφα- το ίδιο ισχύει και για τις ετικέτες των ακμών.Pierre-Antoine Champin, Christine Solnon, "Measuring the Similarity of Labeled Graphs" in:  Lecture Notes in Computer Science, vol. 2689, pp 80–95

Επί παραδείγματι, το γράφημα  με τις δύο κορυφές με τις ετικέτες 1 και 2 έχει έναν μόνο αυτομορφισμό σύμφωνα με τον πρώτο ορισμό, αλλά σύμφωνα με τον δεύτερο ορισμό υπάρχουν δύο αυτομορφισμοί.

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

Κίνητρα

Η τυπική έννοια του "ισομορφισμού", π.χ. του "ισομορφισμού γράφων", αποτυπώνει την άτυπη έννοια ότι ορισμένα αντικείμενα έχουν "την ίδια δομή", αν αγνοήσει κανείς τις επιμέρους διακρίσεις των «ατομικών» συστατικών των εν λόγω αντικειμένων.  Όταν η ατομικότητα των "ατομικών" στοιχείων (κορυφές και ακμές, για τους γράφους) είναι σημαντική για την ορθή αναπαράσταση αυτού που διαμορφώνεται με τους γράφους, το πρότυπο τελειοποιείται με την επιβολή πρόσθετων περιορισμών στη δομή και χρησιμοποιούνται άλλα μαθηματικά αντικείμενα: διγράφοι, γράφοι με ετικέτες, χρωματιστοί γράφοι, δέντρα με ρίζες, κ.λπ. Η σχέση ισομορφισμού μπορεί επίσης να οριστεί για όλες αυτές τις γενικεύσεις των γραφημάτων: η αμφίρριψη ισομορφισμού πρέπει να διατηρεί τα στοιχεία της δομής που καθορίζουν τον εν λόγω τύπο αντικειμένου: τόξα, ετικέτες, χρώματα κορυφών/ακμών, η ρίζα του ριζωμένου δέντρου κ.λπ.

Η έννοια του "ισομορφισμού γράφων" μας επιτρέπει να διακρίνουμε τις ιδιότητες των γράφων που είναι εγγενείς στις δομές των ίδιων των γράφων από τις ιδιότητες που σχετίζονται με τις αναπαραστάσεις των γράφων: σχέδια γράφων, δομές δεδομένων για γράφους, ετικέτες γράφων, κ.λπ. Λόγου χάριν, αν ένας γράφος έχει ακριβώς έναν κύκλο, τότε όλοι οι γράφοι της κλάσης ισομορφισμού του έχουν επίσης ακριβώς έναν κύκλο. Από την άλλη πλευρά, στην κοινή περίπτωση που οι κορυφές ενός γράφου είναι (αναπαριστώνται από) τους ακέραιους αριθμούς 1, 2,... N, τότε η έκφραση

μπορεί να είναι διαφορετική για δύο ισομορφικά γραφήματα.

 Θεώρημα Γουίτνι 

Το θεώρημα ισομορφισμού γράφων Γουίτνι, που παρουσιάστηκε από τον Χάσλερ Γουίτνι, δηλώνει ότι δύο συνδεδεμένα γραφήματα είναι ισομορφικά αν και μόνο αν τα γραφήματα των γραμμών τους είναι ισομορφικά, με μία μόνο εξαίρεση: K3, το πλήρες γράφημα σε τρεις κορυφές, και το πλήρες διμερές γράφημα K1,3, τα οποία δεν είναι ισόμορφα αλλά και τα δύο έχουν το K3 ως γράφημα γραμμής τους. Το θεώρημα του γραφήματος Γουίτνι μπορεί να επεκταθεί σε υπεργράμματα.Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.

Αναγνώριση του ισομορφισμού γράφων

Ενώ ο ισομορφισμός γράφων μπορεί να μελετηθεί με κλασικό μαθηματικό τρόπο, όπως ενδεικτικά αναφέρεται στο θεώρημα Γουίτνι, είναι πλέον αναγνωρισμένο ότι πρόκειται για ένα πρόβλημα που πρέπει να αντιμετωπιστεί με αλγοριθμική προσέγγιση. Το υπολογιστικό πρόβλημα του προσδιορισμού του κατά πόσον δύο πεπερασμένα γραφήματα είναι ισομορφικά ονομάζεται πρόβλημα ισομορφισμού γραφημάτων.

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

Το πρόβλημα του ισομορφισμού γράφων είναι ένα από τα λίγα τυπικά προβλήματα στη θεωρία υπολογιστικής πολυπλοκότητας που ανήκουν στο NP, αλλά δεν είναι γνωστό ότι ανήκουν σε κανένα από τα γνωστά (και, αν P ≠ NP, διαχωρισμένα) υποσύνολά του: P και NP-πλήρες. Είναι ένα από τα δύο μόνο, από τα 12 συνολικά, προβλήματα που αναφέρονται στο  Γκάρι & Τζόνσον ( του οποίου η πολυπλοκότητα παραμένει άλυτη, το άλλο είναι η παραγοντοποίηση ακεραίων αριθμών.  Είναι ωστόσο γνωστό ότι αν το πρόβλημα είναι NP-πλήρες τότε η πολυωνυμική ιεραρχία καταρρέει σε ένα πεπερασμένο επίπεδο.

Τον Νοέμβριο του 2015, ο Λάσλο Μπαμπάι, μαθηματικός και επιστήμονας υπολογιστών στο Πανεπιστήμιο του Σικάγο, ισχυρίστηκε ότι απέδειξε ότι το πρόβλημα του ισομορφισμού γραφημάτων είναι επιλύσιμο σε οιονεί πολυωνυμικό χρόνο.. Δημοσίευσε προκαταρκτικές εκδοχές αυτών των αποτελεσμάτων στα πρακτικά του Συμποσίου για τη Θεωρία της Πληροφορικής του 2016   και του Διεθνούς Συνεδρίου Μαθηματικών του 2018. Τον Ιανουάριο του 2017, ο Μπαμπάι απέσυρε για λίγο τον ισχυρισμό της οιονεί πολυωνυμικότητας και ανέφερε ένα υποεκθετικό όριο πολυπλοκότητας χρόνου. Αποκατέστησε τον αρχικό ισχυρισμό πέντε ημέρες αργότερα. Ως τις 2024, η πλήρης έκδοση της εργασίας του Μπαμπάι στο περιοδικό δεν έχει ακόμη δημοσιευτεί.

Η γενίκευσή του, το πρόβλημα ισομορφισμού υπογράφων, είναι γνωστό ότι είναι NP-πλήρες.

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

Το τεστ ισομορφισμού γράφων Βάισφεϊλερ Λέμαν μπορεί να χρησιμοποιηθεί για τον ευρετικό έλεγχο του ισομορφισμού γράφων. Αν το τεστ αποτύχει, οι δύο γράφοι εισόδου είναι εγγυημένα μη ισομορφικοί. Εάν η δοκιμή επιτύχει, οι γράφοι μπορεί να είναι ισόμορφοι ή όχι. Υπάρχουν γενικεύσεις του αλγορίθμου δοκιμής που εγγυώνται την ανίχνευση ισομορφισμών, ωστόσο ο χρόνος εκτέλεσής τους είναι εκθετικός.

Ένας άλλος γνωστός αλγόριθμος για τον ισομορφισμό γράφων είναι ο αλγόριθμος vf2, που αναπτύχθηκε από τους Κορντελιά και αλ. (Cordella et al.) το 2001. Ο αλγόριθμος vf2 είναι ένας αλγόριθμος αναζήτησης σε βάθος που προσπαθεί να δημιουργήσει έναν ισομορφισμό μεταξύ δύο γράφων σταδιακά. Χρησιμοποιεί ένα σύνολο κανόνων εφικτότητας για την αποκοπή του χώρου αναζήτησης, επιτρέποντάς του να χειρίζεται αποτελεσματικά γράφους με χιλιάδες κόμβους. Ο αλγόριθμος vf2 χρησιμοποιήθηκε ευρέως σε διάφορες εφαρμογές, όπως η αναγνώριση προτύπων, η όραση υπολογιστή και η βιοπληροφορική. Ενώ έχει εκθετική χρονική πολυπλοκότητα στη χειρότερη περίπτωση, αποδίδει καλά στην πράξη για πολλούς τύπους γράφων.

 Εξωτερικοί σύνδεσμοι 
English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
ΑΓΓΛΟΕΛΛΗΝΙΚΟ. ΛΕΞΙΚΟ. ΜΑΘΗΜΑΤΙΚΩΝ. ΟΡΩΝ Αριάδνη Καλογερόπουλου. Μίλτος Γκίκας — Δ. Καραπαννακης — Μ. Λάμπρου. 
 Θεωρία Ομάδων-Πανεπιστήμιο Κρήτης
 Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
 Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
 Θεωρία Αριθμών και Εφαρμογές
 Υπολογιστική Θεωρία Αριθμών
 Καμπυλότητες και γεωμετρία του Riemann σε διαφορίσιμες πολλαπλότητες Εθνικό Αρχείο Διδακτορικών Διατριβών
 Μέθοδοι μηχανικής μάθησης βασισμένες σε έλεγχο μονοτροπικότητας Εθνικό Αρχείο Διδακτορικών Διατριβών
  Παράμετροι και Στατιστικά. Διωνυμική και Κανονική Κατανομή
 Wolfram Mathematica Online Integrator
  A Table of Integrals of the Error Functions

 Δείτε επίσης 

 Απαγορευτική αρχή του Πάουλι
 Μορφοκλασματική διάσταση
 Ομοπαραλληλική γεωμετρία
 Αλγεβρική θεωρία αριθμών
 Άρθουρ Στάνλεϋ Έντινγκτον
 Μοναδιαία βηματική συνάρτηση
 Σουμπραμανιάν Τσαντρασεκάρ
 Ευκλείδειος χώρος
 Αρχιμήδεια ιδιότητα
 Βαθμός (γραμμική άλγεβρα)
 Εφαρμοσμένα μαθηματικά
 Υπολογιστική ρευστοδυναμική
 Αβελιανή ομάδα
 Σύνθεση συνάρτησης
 Καρτεσιανό σύστημα συντεταγμένων
 Θεμελιώδες θεώρημα αριθμητικής
 Αλγεβρική γεωμετρία
 Ένα προς ένα
 Συνήθης διαφορική εξίσωση
 Γραμμική απεικόνιση
 Αβελιανή ομάδα

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











Παραπομπές

.
.
.
.















 Πηγές 






 Wendelin Degen, Lothar Profke: Grundlagen der affinen und euklidischen Geometrie. Teubner, Stuttgart 1976, ISBN 3-519-02751-8.
 Hans Freudenthal: Mathematik als pädagogische Aufgabe. Band 1. Klett, Stuttgart 1973, ISBN 3-12-983220-3.
 Thomas W. Hungerford: Algebra (= Graduate Texts in Mathematics. Bd. 73). 5th printing. Springer, New York NY u. a. 1989, ISBN 0-387-90518-9.

Κατηγορία:Μορφισμοί
Κατηγορία:Θεωρία γράφων