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

Στη θεωρία γράφων, ένας **ισομορφισμός γραφημάτων** *G* και *H* είναι μια αμφίρριψη μεταξύ των συνόλων κορυφών των *G* και *H*
:  f \colon V(G) \to V(H) 
έτσι ώστε οποιεσδήποτε δύο κορυφές *u* και *v* του *G* να είναι παρακείμενες στο *G* αν και μόνο αν οι f(u) και f(v) είναι παρακείμενες στο *H*. Αυτό το είδος της αμφίρριψης περιγράφεται συνήθως ως "αμφίρριψη που διατηρεί τη δομή", σύμφωνα με τη γενική έννοια του ισομορφισμού που είναι μια structure-preserving bijection.

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

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

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

## Μεταβολές

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

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

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

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

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

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

## Κίνητρα

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

Η έννοια του "ισομορφισμού γράφων" μας επιτρέπει να διακρίνουμε τις ιδιότητες των γράφων που είναι εγγενείς στις δομές των ίδιων των γράφων από τις ιδιότητες που σχετίζονται με τις αναπαραστάσεις των γράφων: σχέδια γράφων, δομές δεδομένων για γράφους, ετικέτες γράφων, κ.λπ. Λόγου χάριν, αν ένας γράφος έχει ακριβώς έναν κύκλο, τότε όλοι οι γράφοι της κλάσης ισομορφισμού του έχουν επίσης ακριβώς έναν κύκλο. Από την άλλη πλευρά, στην κοινή περίπτωση που οι κορυφές ενός γράφου είναι (*αναπαριστώνται* από) τους ακέραιους αριθμούς 1, 2,... *N*, τότε η έκφραση
:\sum_{v \in V(G)} v\cdot\text{deg }v
μπορεί να είναι διαφορετική για δύο ισομορφικά γραφήματα.

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

Το **θεώρημα ισομορφισμού γράφων Γουίτνι**, που παρουσιάστηκε από τον Χάσλερ Γουίτνι, δηλώνει ότι δύο συνδεδεμένα γραφήματα είναι ισομορφικά αν και μόνο αν τα γραφήματα των γραμμών τους είναι ισομορφικά, με μία μόνο εξαίρεση: *K*3, το πλήρες γράφημα σε τρεις κορυφές, και το πλήρες διμερές γράφημα *K*1,3, τα οποία δεν είναι ισόμορφα αλλά και τα δύο έχουν το *K*3 ως γράφημα γραμμής τους. Το θεώρημα του γραφήματος Γουίτνι μπορεί να επεκταθεί σε υπεργράμματα.

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

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

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

Το πρόβλημα του ισομορφισμού γράφων είναι ένα από τα λίγα τυπικά προβλήματα στη θεωρία υπολογιστικής πολυπλοκότητας που ανήκουν στο NP, αλλά δεν είναι γνωστό ότι ανήκουν σε κανένα από τα γνωστά (και, αν P&nbsp;≠&nbsp;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.

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