Ομοιομορφισμός (γραφικά)

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

 Υποδιαίρεση και εξομάλυνση 
Γενικά, μια υποδιαίρεση (γνωστή και ως επέκταση)Trudeau (1993), σελ. 76: Definition 20 ενός γραφήματος G είναι μια γραφική παράσταση που προκύπτει από την υποδιαίρεση των ακμών του G. Η υποδιαίρεση κάποιας ακμής e με άκρα {u,v} παράγει ένα γράφημα που περιέχει μια νέα κορυφή w η οποία διαιρεί την ακμή e σε δύο νέα ακμές, την {u,w} και την {w,v}.

Για παράδειγμα, η ακμή e, με άκρα {u,v}:
150px
μπορεί να υποδιαιρεθεί σε δύο ακμές, e1 και e2, συνδεδεμένες σε μια νέα κορυφή w:
150px

Η εξομάλυνση (γνωστή και ως λείανση) είναι η αντίστροφη λειτουργία, η οποία εξομαλύνει μια κορυφή w που σχετίζεται με ένα ζεύγος ακμών (e1 και e2) που προσπίπτουν στην κορυφή w, αφαιρώντας τις δύο ακμές που περιέχουν την w και αντικαθιστώντας τις ακμές (e1 και e2) με μια νέα ακμή (e) που συνδέει τις δύο άλλες κορυφές του ζεύγους (u και w). Εδώ τονίζεται ότι μόνο οι 2-δύναμες κορυφές μπορούν να λειανθούν.

Για παράδειγμα, το απλά συνδεδεμένο γράφημα με δύο ακμές, e1 {u,w} και e2 {w,v}: 
150px
έχει μια κορυφή w που μπορεί να εξομαλυνθεί, έχοντας ως αποτέλεσμα:
150px

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

 Βαρυκεντρικές υποδιαιρέσεις 
Η βαρυκεντρική υποδιαίρεση υποδιαιρεί την κάθε ακμή ενός γραφήματος. Αυτή είναι μια ειδική υποδιαίρεση, διότι οδηγεί πάντα σε ένα διμερές γράφημα. Αυτή η διαδικασία μπορεί να επαναληφθεί, έτσι ώστε η ν-οστή βαρυκεντρική υποδιαίρεση να είναι η βαρυκεντρική υποδιαίρεση της ν-1-στής βαρυκεντρικής υποδιαίρεσης του γραφήματος. Μια τέτοια δεύτερη υποδιαίρεση είναι πάντα ένα απλό γράφημα.

 Ενσωμάτωση σε μια επιφάνεια 
Είναι προφανές ότι η υποδιαίρεση ενός γραφήματος διατηρεί επιπεδότητα. Το Θεώρημα του Κουρατόφσκι (Kazimierz Kuratowski, 1930), αναφέρει ότι:

 Ένα πεπερασμένο γράφημα είναι επίπεδο αν και μόνο αν δεν περιέχει υπογραφήματα ομοιογραφικά στο K5 (πλήρες γράφημα σε πέντε κορυφές) και στο K3,3 (πλήρες διμερές γράφημα σε έξι κορυφές, τρεις από τις οποίες συνδέονται με κάθε μία από τις άλλες τρεις).

Εκ των πραγμάτων, ένα ομοιομορφικό γράφημα στο K5 και K3,3 ονομάζεται υπογράφημα Κουρατόφσκι.

Μια γενίκευση, που απορρέει από το θεώρημα Ρόμπερτσον-Σέιμουρ, υποστηρίζει ότι για κάθε ακέραιο g, υπάρχει ένα πεπερασμένο σύνολο απόφραξης γραφημάτων:

Το σύνολο αυτό είναι τέτοιο, ώστε ένα γράφημα H να είναι ενσωματωμένο σε μια επιφάνεια γένους g, αν και μόνο αν το H δεν περιέχει ομοιογραφικό αντίγραφο οποιουδήποτε εκ των . Για παράδειγμα, το  που περιέχει υπογραφήματα Κουρατόφσκι.

 Παράδειγμα 
Στο παρακάτω παράδειγμα, τα γραφήματα G και Η είναι ομοιομορφικά γραφήματα.
   150px|γράφημα H    150px|γράφημα G

Αν το G' είναι το γράφημα που δημιουργείται από την υποδιαίρεση των εξωτερικών ακμών του G και H' είναι το γράφημα που δημιουργείται από την υποδιαίρεση του εσωτερικής ακμής του Η, τότε τα G' και Η' έχουν ένα παρόμοιο γράφημα στο σχεδιασμό:

 150px|γράφημα G

Ως εκ τούτου, υπάρχει ένας ισομορφισμός μεταξύ των G' και H', που σημαίνει ότι τα G και H είναι ομοιομορφικά.

 Παραπομπές 

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



Κατηγορία:Γραφικά υπολογιστών
Κατηγορία:Θεωρία γράφων
Κατηγορία:Μορφισμοί