Θεώρημα δομής γράφων

Στα μαθηματικά, το θεώρημα δομής γράφων είναι ένα σημαντικό αποτέλεσμα στον τομέα της θεωρίας γράφων. Το αποτέλεσμα δημιουργεί μια βαθιά και θεμελιώδη σχέση μεταξύ της θεωρίας των ελασσόνων γραφημάτων και τοπογραφικών εμφωλευμάτων. Το θεώρημα αναφέρεται στο δέκατο έβδομο αιώνα σε μία σειρά από 23 σελίδες που γράφτηκαν από τον Neil Robertson και Paul Seymour. Η απόδειξη του είναι πολύ μεγάλη και περίπλοκη. Οι Kawarabayashi & Mohar (2007) και Lovász (2006) είναι έρευνες προσβάσιμες σε μη ειδικούς, που περιγράφουν το θεώρημα και τις συνέπειές του.

Δημιουργία και κίνητρο για το θεώρημα

Ένα μικρό κομμάτι ενός γραφήματος G είναι οποιοδήποτε γράφημα H που είναι ισόμορφο με ένα γράφημα που μπορεί να ληφθεί από ένα υπογράφημα του G αν συσταλλούν κάποιες άκρες του. Αν το G δεν έχει το γράφημα H ως κομμάτι του, τότε λέμε ότι το G είναι Η-ελεύθερο. Ας είναι H ένα σταθερό γράφημα . Διαισθητικά, αν το G είναι ένα τεράστιο H-ελεύθερο γράφημα, τότε θα έπρεπε να υπάρχει ένας "καλός λόγος" για αυτό. Το θεώρημα δομής γράφων παρέχει έναν "καλό λόγο" για τη μορφή μιας πρόχειρης περιγραφή της δομής του G. Στην ουσία, κάθε H-ελεύθερο γράφημα G πάσχει από μία από τις δύο διαρθρωτικές αδυναμίες: είτε το γράφημα του G είναι "πάρα πολύ λεπτό" για να έχει το H ως μικρό κομμάτι του, ή το G μπορεί να είναι (σχεδόν) τοπολογικά ενσωματωμένο σε μια επιφάνεια που είναι πάρα πολύ απλό να ενσωματώσουμε και το H. Ο πρώτος λόγος ισχύει αν το H είναι μια επίπεδη γραφική παράσταση, ενώ και οι δύο λόγοι ισχύουν εάν η H δεν είναι επίπεδη. Πρέπει πρώτα να κάνουμε ακριβείς τις έννοιες αυτές.

Πλάτος δέντρου

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

Πόρισμα 1. Για κάθε επίπεδο γράφημα H, υπάρχει ένας θετικός ακέραιος k τέτοιος ώστε κάθε H–ελεύθερο γράφημα να έχει πλάτος δέντρου μικρότερο από k.

Είναι ατυχές το ότι η τιμή του k που αναφέρθηκε στο Πόρισμα 1 είναι γενικά πολύ μεγαλύτερη από το πλάτος του δέντρου H (μια αξιοσημείωτη εξαίρεση είναι όταν Η = Κ₄, το πλήρες γράφημα σε τέσσερις κορυφές, για το οποίο k = 3). Αυτός είναι ένας λόγος που το θεώρημα δομής γράφων χρησιμοποιείται για να περιγράψει την "τραχιά δομή" των H-ελεύθερων γραφημάτων.

Επιφανειακά εμφυτεύματα

Χονδρικά, μία επιφάνεια είναι ένα σύνολο σημείων με μία τοπική τοπολογική δομή ενός δίσκου. Οι επιφάνειες χωρίζονται σε δύο άπειρες οικογένειες: στις επιφάνειες  προσανατολισμού οι οποίες περιλαμβάνουν τη σφαίρα, τον τόρος, το διπλό τόρος κ.ο.κ. Οι μη προσανατολίσιμες επιφάνειες περιλαμβάνουν το πραγματικό προβολικό επίπεδο, το μπουκάλι Klein κ.ο.κ. Ένα γράφημα ενσωματώνεται σε μια επιφάνεια, αν μπορεί να γίνει η γραφική παράσταση στην επιφάνεια ως ένα σύνολο σημείων (κορυφές) και τόξων (άκρα) που δεν διασχίζουν ή αγγίζουν το ένα το άλλο, εκτός από την περίπτωση που οι ακμές και κορυφές είναι προσπίπτουσες ή γειτονικές. Ένα γράφημα είναι επίπεδο, αν ενσωματώνεται στη σφαίρα. Εάν ένα γράφημα G ενσωματώνεται σε μια συγκεκριμένη επιφάνεια τότε κάθε μικρό γράφημα G ενσωματώνεται επίσης στην ίδια επιφάνεια. Ως εκ τούτου, ένας "καλός λόγος" για το G να είναι H–ελεύθερο είναι ότι το G ενσωματώνεται σε μια επιφάνεια στην οποία δεν ενσωματώνεται το H.

Όταν το H δεν είναι επίπεδο γράφημα, το θεώρημα δομής γράφων μπορεί να αντιμετωπίζεται ως μια τεράστια γενίκευση του θεωρήματος Kuratowski. Μια έκδοση αυτού του θεωρήματος αποδεικνύεται από τον Wagner (1937) ο οποίος αναφέρει ότι αν ένα γράφημα G είναι και Κ₅–ελεύθερο και K_3,3-ελεύθερο, τότε το G είναι επίπεδο γράφημα. Αυτό το θεώρημα παρέχει έναν "καλό λόγο" για να μην έχει το γράφημα G τα Κ₅ ή K_3,3 ως μικρότερα γραφήματα. Συγκεκριμένα, το γράφημα G ενσωματώνεται στη σφαίρα, ενώ ούτε το Κ₅ ούτε το K_3,3 ενσωματώνονται στη σφαίρα. Δυστυχώς, αυτή η έννοια του "καλού λόγου" δεν είναι αρκετά εξελιγμένη για το θεώρημα δομής γράφων. Απαιτούνται δύο ακόμη έννοιες: κλίκες ποσών και δίνες.

Κλίκα Ποσών

Μια κλίκα σε ένα γράφημα G είναι οποιοδήποτε σύνολο των κορυφών που βρίσκονται ανά ζεύγη δίπλα στο G. Για έναν μη αρνητικό ακέραιο k, μια k-κλίκα-άθροισμα των δύο γραφημάτων G και Κ είναι οποιαδήποτε γραφική παράσταση που λαμβάνεται με την επιλογή ενός μη αρνητικού ακεραίου m ≤ k, επιλέγοντας κλίκα μεγέθους m σε κάθε ένα από τα G και Κ, προσδιορίζοντας τις δύο κλίκες σε μία ενιαία κλίκα μεγέθους m, και μετά διαγράφοντας μηδέν ή περισσότερες από τις ακμές που ενώνουν τις κορυφές στη νέα κλίκα.

Αν G₁, G₂, ... , G_n είναι μια λίστα των γραφημάτων, τότε μπορούμε να παράγουμε ένα νέο γράφημα ενώνοντας τον κατάλογο των γραφημάτων μέσω k-κλίκας ποσών. Δηλαδή, παίρνουμε μια k-κλίκα-άθροισμα των G₁ και G₂, μετά παίρνουμε μια k-κλίκα-άθροισμα του G₃ με το γράφημα που προκύπτει, και ούτω καθεξής. Ένα γράφημα έχει πλάτος δέντρου το πολύ k αν μπορεί να ληφθεί μέσω της k-κλίκας ποσών από μια λίστα γραφημάτων, όπου κάθε γράφημα στη λίστα έχει το πολύ k + 1 κορυφές.

Το πόρισμα 1 μας δείχνει ότι η k-κλίκα ποσών των μικρών γραφημάτων περιγράφει την τραχιά δομή H-ελευθέρων γραφημάτων όταν η H είναι επίπεδη. Όταν η H είναι μη-επίπεδη, θα πρέπει επίσης να λάβουμε υπ’ όψη μια k-κλίκα ποσών από μια λίστα γραφημάτων, καθένα από τα οποία είναι ενσωματωμένα σε μια επιφάνεια. Το ακόλουθο παράδειγμα με H = Κ₅ απεικονίζει το σημείο αυτό. Το Κ₅ γράφημα ενσωματώνεται σε κάθε επιφάνεια εκτός από την σφαίρα. Ωστόσο, υπάρχουν Κ₅-ελεύθερα γραφήματα που είναι μακριά από το να είναι επίπεδα. Πιο συγκεκριμένα , η 3-κλίκα-άθροισμα από οποιαδήποτε λίστα επίπεδων γραφημάτων έχει ως αποτέλεσμα ένα γράφημα Κ₅–ελεύθερο. Ο Wagner (1937) προσδιόρισε την ακριβή δομή των Κ₅-ελευθέρων γραφημάτων, ως μέρος ενός συμπλέγματος αποτελεσμάτων που είναι γνωστά ως θεώρημα του Wagner:

Θεώρημα 2. Αν G είναι Κ₅-ελεύθερη, τότε το G μπορεί να ληφθεί μέσω της 3–κλίκας ποσών από έναν κατάλογο επίπεδων γραφημάτων, καθώς και από αντίγραφα μιας ειδικής μη-επίπεδης γραφικής παράστασης που έχει 8–κορυφές.

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

Δίνες (πρόχειρη περιγραφή)

Θα μπορούσε κανείς να μπει στον πειρασμό να εικάσει ότι ένα ανάλογο του Θεωρήματος 2 ισχύει και για γραφήματα H εκτός του Κ₅. Ίσως είναι αλήθεια ότι: για κάθε μη επίπεδο γράφημα H, υπάρχει ένας θετικός ακέραιος k τέτοιος ώστε κάθε H-ελεύθερο γράφημα μπορεί να ληφθεί μέσω μιας k-κλίκας ποσών από μια λίστα γραφημάτων, καθένα από τα οποία είτε έχει το πολύ k κορυφές ή ενσωματώνεται σε κάποια επιφάνεια που δεν ενσωματώνεται η H. Δυστυχώς, η δήλωση αυτή δεν είναι ακόμη αρκετά εκλεπτυσμένη για να είναι αληθινή. Θα πρέπει να επιτρέψουμε σε κάθε ενσωματωμένο γράφημα G_i να "εξαπατήσει" με δύο συγκεκριμένους τρόπους. Κατ 'αρχάς, θα πρέπει να επιτρέψουμε μια περιορισμένη σειρά από θέσεις στην επιφάνεια στην οποία μπορούμε να προσθέσουμε μερικές νέες κορυφές και ακμές που επιτρέπεται να διασχίζουν η μία την άλλη με έναν τρόπο περιορισμένης πολυπλοκότητας. Αυτές οι τοποθεσίες ονομάζονται δίνες. Η "πολυπλοκότητα" ενός στροβίλου περιορίζεται από μια παράμετρο που ονομάζεται βάθος, που συνδέεται στενά με το πλάτος της διαδρομής. Ο αναγνώστης μπορεί να προτιμήσει να αναβάλλει την ανάγνωση της ακόλουθης ακριβής περιγραφής της δίνης βάθους k. Δεύτερον, πρέπει να επιτρέψουμε ένα περιορισμένο αριθμό νέων κορυφών για να προσθέσουμε σε κάθε ένα από τα ενσωματωμένα γραφήματα με δίνες.

Δίνες (ακριβής ορισμός)

Το πρόσωπο ενός ενσωματωμένου γραφήματος είναι ένα ανοικτό 2-κελί στην επιφάνεια που δεν συνδέεται με τη γραφική παράσταση, αλλά του οποίου το σύνορο είναι η ένωση μερικών άκρων του ενσωματωμένου γραφήματος. Ας είναι F ένα πρόσωπο ενός ενσωματωμένου γραφήματος G και v₀, v₁, ... , v_{n - 1}, v_n = v₀ οι κορυφές που βρίσκονται στο όριο της F (στην εν λόγω εγκύκλια σειρά). Ένα κυκλικό διάστημα για το F είναι ένα σύνολο από κορυφές της μορφής {v_a , v_{a + 1}, ... , v_{a + s}}, όπου a και s είναι ακέραιοι και οι δείκτες μειώνονται κατά modulo n. Ας είναι Λ μια πεπερασμένη λίστα κυκλικών διαστημάτων F. Κατασκευάζουμε ένα νέο γράφημα ως εξής: Για κάθε κυκλικό διάστημα L στην Λ προσθέτουμε μια νέα κορυφή v_L που ενώνει στο μηδέν ή περισσότερες από τις κορυφές στο L. Τέλος , για κάθε ζεύγος διαστημάτων {L , M} στο Λ, μπορούμε να προσθέσουμε μια άκρη που ενώνει το v_L στο v_M με την προϋπόθεση ότι τα L και Μ έχουν μη κενή τομή. Το προκύπτον γράφημα μπορεί να ληφθεί από το G, με την προσθήκη μιας δίνης βάθους το πολύ k (στο πρόσωπο F) υπό την προϋπόθεση ότι καμία κορυφή στο όριο του F δεν εμφανίζεται σε περισσότερα από k διαστήματα του Λ.

Δήλωση του θεωρήματος δομή γράφημα

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

1.   Ξεκινάμε με μια λίστα γραφημάτων, όπου κάθε γράφημα στη λίστα είναι ενσωματωμένο σε μια επιφάνεια επί της οποίας η Η δεν ενσωματώνεται,

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

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

4.   Τέλος, ενώνουμε μέσω μιας k-κλίκας ποσών την προκύπτουσα λίστα των γραφημάτων.

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

Βελτιώσεις

Ενισχυμένες εκδόσεις του θεωρήματος δομής γράφων είναι δυνατές, ανάλογα με το σύνολο H των απαγορευμένων ελασσόνων. Για παράδειγμα, όταν μία από τις γραφικές παραστάσεις στο H είναι επίπεδη, τότε κάθε H ελάσσονος σημασίας χωρίς γράφημα έχει μια αποσύνθεση δέντρου οριοθετούμενου πλάτους. Ισοδύναμα, μπορεί να παρασταθεί ως κλίκα-άθροισμα των γραφημάτων του σταθερού μεγέθους. Όταν μπορεί να γίνει ένα από τα γραφήματα στο H στο επίπεδο με μία μόνο διέλευση, τότε τα H ελάσσονος σημασίας ελεύθερα γραφήματα ορίζουν μια αποσύνθεση ως μια κλίκα-άθροισμα των γραφημάτων σταθερού μεγέθους και γραφήματα οριοθετούμενου γένους, χωρίς δίνες. Μια διαφορετική ενίσχυση είναι επίσης γνωστή, όταν ένα από τα γραφήματα στο H είναι μια κορυφή γράφημα.

Σημειώσεις

1. Graph Minors V.
2. Robertson & Seymour (1993); Demaine, Hajiaghayi & Thilikos (2002).
3. Demaine, Hajiaghayi & Kawarabayashi (2009).