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

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

Υποδιαίρεση και εξομάλυνση[Επεξεργασία | επεξεργασία κώδικα]

Γενικά, μια υποδιαίρεση (γνωστή και ως επέκταση)^[1] ενός γραφήματος G είναι μια γραφική παράσταση που προκύπτει από την υποδιαίρεση των ακμών του G. Η υποδιαίρεση κάποιας ακμής e με άκρα {u,v} παράγει ένα γράφημα που περιέχει μια νέα κορυφή w η οποία διαιρεί την ακμή e σε δύο νέα ακμές, την {u,w} και την {w,v}.

Για παράδειγμα, η ακμή e, με άκρα {u,v}:

μπορεί να υποδιαιρεθεί σε δύο ακμές, e₁ και e₂, συνδεδεμένες σε μια νέα κορυφή w:

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

Για παράδειγμα, το απλά συνδεδεμένο γράφημα με δύο ακμές, e₁ {u,w} και e₂ {w,v}:

έχει μια κορυφή w που μπορεί να εξομαλυνθεί, έχοντας ως αποτέλεσμα:

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

Βαρυκεντρικές υποδιαιρέσεις[Επεξεργασία | επεξεργασία κώδικα]

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

Ενσωμάτωση σε μια επιφάνεια[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

$L(g)=\{G_{i}^{(g)}\}$

Το σύνολο αυτό είναι τέτοιο, ώστε ένα γράφημα H να είναι ενσωματωμένο σε μια επιφάνεια γένους g, αν και μόνο αν το H δεν περιέχει ομοιογραφικό αντίγραφο οποιουδήποτε εκ των $G_{i}^{(g)}$ . Για παράδειγμα, το $L(0)=\{K_{5},K_{3,3}\}$ που περιέχει υπογραφήματα Κουρατόφσκι.

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Στο παρακάτω παράδειγμα, τα γραφήματα G και Η είναι ομοιομορφικά γραφήματα.

G

H

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

$G',H'$

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

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Trudeau (1993), σελ. 76: Definition 20
↑ LaPaugh, Andrea S.; Rivest, Ronald L. (1980). «The subgraph homeomorphism problem». Journal of Computer and System Sciences 20 (2): 133–149. doi:10.1016/0022-0000(80)90057-4. MR 574589. .

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Trudeau, Richard J. (1993). Introduction to Graph Theory. New York: Dover Pub. ISBN 978-0-486-67870-2. Ανακτήθηκε στις 8 Αυγούστου 2012.
Yellen, Jay· Gross, Jonathan L. (2005). Graph Theory and Its Applications. Discrete Mathematics and Its Applications (2η έκδοση). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-58488-505-4.

[1] Trudeau (1993), σελ. 76: Definition 20

[2] LaPaugh, Andrea S.; Rivest, Ronald L. (1980). «The subgraph homeomorphism problem». Journal of Computer and System Sciences 20 (2): 133–149. doi:10.1016/0022-0000(80)90057-4. MR 574589. .

[1]

[2]