Θεώρημα διαχωρισμού του επιπέδου

Στη θεωρία γραφημάτων, το θεώρημα διαχωριστικού επιπέδου είναι μια μορφή ισοπεριμετρικών ανισοτήτων για επίπεδες γραφικές παραστάσεις, που αναφέρει ότι οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να χωριστεί σε μικρότερα κομμάτια αφαιρώντας ένα μικρό αριθμό κορυφών. Συγκεκριμένα, η απομάκρυνση της O(√n) κορυφής από ένα γράφημα με n-κορυφές (όπου το O επικαλείται επικαλείται μεγάλο O συμβολισμό) μπορεί να χωρίσει το γράφημα σε ασυνεχείς υπογράφους καθένα από τα οποία έχει το πολύ 2n / 3 κορυφές.
Μια ηπιότερη μορφή του θεωρήματος διαχωρισμού με O(√n log n) κορυφές στο διαχωριστή αντί για O(√n) αρχικά αποδεικνύεται από τον Ungar (1951), καθώς και η μορφή με την στενή ασύμπτωτη δεσμεύεται από το μέγεθος της διαχωριστικής που πρωτοαποδείχτηκε από τον Lipton & Tarjan (1979). Δεδομένου του έργου τους, το θεώρημα διαχωρισμού έχει αποδειχτεί ξανά με διάφορους τρόπους,ο σταθερός στη θέση O(√n)όρος του θεωρήματος έχει βελτιωθεί, και έχει επεκταθεί σε ορισμένες κατηγορίες των μη επίπεδων γραφικών παραστάσεων.
Η επαναλαμβανόμενη εφαρμογή του θεωρήματος διαχωρισμού παράγει μια ιεραρχία ξεχωριστή η οποία μπορεί να λάβει τη μορφή είτε ενός βασικού μέρους αποσύνθεσης (δέντρου) ή μιας διακλαδωσης-αποσύνθεσης του γραφήματος. Διαχωριστικές ιεραρχίες μπορεί να χρησιμοποιηθούν για να επινοήσουν αποδοτικούς αλγορίθμους του τύπου διαίρει και βασίλευε για επίπεδα γραφήματα, και δυναμικοί προγραμματισμοί αυτών των ιεραρχιών μπορούν να χρησιμοποιηθούν για να σχεδιάσουν εκθετικό χρόνο και σταθερών παραμέτρων εύκολων αλγορίθμων για την επίλυση NP-hard προβλημάτων βελτιστοποίησης σε αυτά τα γραφήματα. Οι διαχωριστικές ιεραρχίες μπορεί επίσης να χρησιμοποιηθούν σε φωλιασμένη ανατομή, μια αποτελεσματική παραλλαγή της απαλοιφής Gauss για την επίλυση αραιών συστημάτων γραμμικών εξισώσεων που προκύπτουν από μεθόδους πεπερασμένων στοιχείων.

Δήλωση του θεωρήματος

Όπως συνήθως αναφέρεται, το θεώρημα διαχωρισμού αναφέρει ότι, σε κάθε γράφημα με n επίπεδη κορυφή G = (V,E), υπάρχει μια διαίρεση των κορυφών του G σε τρία σύνολα A, S, και B, έτσι ώστε καθένα από τα A και B να έχει το πολύ 2n/3 κορυφές, S έχει O(√n)κορυφές, και δεν υπάρχουν άκρες με ένα τελικό σημείο A και ένα τελικό σημείο στο B. Δεν είναι υποχρεωτικό ότι οι τύποι A ή B συνδέονται με το γράφημα του G.Το S ονομάζεται διαχωρισμός για αυτή την κατάτμηση.
Μια ισοδύναμη διατύπωση είναι ότι τα άκρα ενός οπουδήποτε γραφήματος G με επίπεδη κορυφή n μπορεί να υποδιαιρεθεί σε δύο άκρο-ασυνεχείς υπογράφους G₁ και G₂ με τέτοιο τρόπο ώστε και οι δύο υπογράφοι να έχουν τουλάχιστον n/3 κορυφές και είναι τέτοιες ώστε το σημείο τομής των συνόλων κορυφών των δύο υπογράφων έχει O(√n) ) κορυφές σε αυτό. Μια τέτοια διαίρεση είναι γνωστή ως διαχωρισμός. Αν ο διαχωρισμός είναι δεδομένος, τότε η τομή των συνόλων των κορυφών σχηματίζει ένα διαχωριστικό, και οι κορυφές που ανήκουν σε έναν υπογράφο, αλλά όχι η άλλη μορφή των διαχωρισμένων υποσυνόλων που έχουν το πολύ 2n/3 3 κορυφές. Από την άλλη μεριά, εφόσον υπάρχει μια διαίρεση σε τρία σύνολα A, S, και B που πληρούν τις προϋποθέσεις του θεωρήματος διαχωριστικού επιπέδου, τότε μπορεί κάποιος να σχηματίσει ένα διαχωρισμό στον οποίο τα άκρα με ένα τελικό σημείο A να ανήκει στην G₁, , οι άκρες με ένα τελικό σημείο στο B να ανήκουν στην G₂, και τα υπόλοιπα άκρα (με τα δύο τελικά σημεία S) να κατανεμηθούν αυθαίρετα.
Η σταθερά των 2/3 στη δήλωση του θεωρήματος διαχωριστικού είναι αυθαίρετο και ίσως μπορεί να αντικατασταθεί από οποιοδήποτε άλλο αριθμό στο ανοικτό διάστημα (1/2, 1), χωρίς να αλλάζει τη μορφή του θεωρήματος: μια διαίρεση σε πιο ίσα υποσύνολα μπορεί να ληφθεί από ακόμα λιγότερες διαιρέσεις κατ 'επανάληψη με τη διάσπαση των μεγαλύτερων συνόλων σε άνισες διαμερίσεις που να ομαδοποιούν τα συνδεδεμένα συστατικά που προκύπτουν.

Παράδειγμα

Σκεφτείτε ένα γράφημα πλέγματος με r στήλες και c γραμμές; ο αριθμός n των κορυφών ισούται με rc. Για παράδειγμα, στην απεικόνιση, r = 5, c = 8, και n = 40. Αν το r είναι περιττό, υπάρχει μια ενιαία κεντρική σειρά, και από την άλλη μεριά υπάρχουν δύο σειρές το ίδιο κοντά στο κέντρο.Ομοίως, αν το c είναι περιττό, υπάρχει μια ενιαία κεντρική στήλη, και από την άλλη μεριά υπάρχουν δύο στήλες το ίδιο κοντά στο κέντρο. Επιλέγοντας το S να είναι οποιαδήποτε από αυτές τις κεντρικές γραμμές ή στήλες, και απομακρύνοντας το S από το γράφημα, διαιρείται το γράφημα σε δύο μικρότερα συνδεδεμένα γραφήματα A και B, το καθένα από τα οποία έχει το πολύ n/2 κορυφές. Αν το r ≤ c (όπως στην εικόνα), ), τότε, επιλέγοντας μία κεντρική στήλη θα μας δώσει ένα διαχωριστικο S με r ≤ √n κορυφές, και ομοίως,αν c ≤ rτότε, επιλέγοντας μία κεντρική γραμμή θα δώσει ένα διαχωριστικό με το πολύ √n κορυφές. . Έτσι, κάθε γράφημα πλέγματος έχει ένα διαχωριστή S με μέγεθος το πολύ √n, η απομάκρυνση της οποίας χωρίζεται σε δύο συνδεδεμένα συστατικά, το καθένα με μέγεθος το πολύ n/2.
Το θεώρημα διαχωριστικού επιπέδου αναφέρει ότι ένα παρόμοιο διαχωριστικό μπορεί να κατασκευαστεί σε οποιαδήποτε επίπεδο γράφημα. Η περίπτωση της αυθαίρετων επίπεδων γραφημάτων διαφέρει από την περίπτωση των γραφημάτων πλέγματος στο ότι ο διαχωριστής έχει μέγεθος O(√n) ), αλλά ίσως μπορεί να είναι μεγαλύτερο από √n, το όριο του μεγέθους των δύο υποσυνόλων A και B (στις πιο κοινές εκδόσεις του θεωρήματος) είναι 2n/3 και όχι n/2, και οι δυο υποομάδες A δεν χρειάζεται από μόνες τους να συγκροτήσουν συνδεδεμένα γραφήματα.

Πρώτο-ευρύ layering

Οι Lipton & Tarjan (1979) αυξάνουν το δοθέν επίπεδο γράφημα με πρόσθετες ακμές, αν είναι απαραίτητο, έτσι ώστε να επιτυγχάνεται το μέγιστο επίπεδο (κάθε μορφή σε μια επίπεδη ενσωμάτωση είναι ένα τρίγωνο). Στην συνέχεια εκτελούν μια πρώτη αναζήτηση, ριζωμένη σε μια αυθαίρετη κορυφή v, και κατανείμουν τις κορυφές σε επίπεδα ανάλογα με την απόσταση τους από την κορυφή v. Αν το l₁ είναι το μεσαίο επίπεδο (δηλαδή το επίπεδο, όπου ο αριθμός των κορυφών σε υψηλότερα και χαμηλότερα επίπεδα είναι και τα δύο το πολύ n/2) τότε πρέπει να υπάρχουν τα επίπεδα l₀ και l₂ που είναι O(√n) βήματα πάνω και κάτω από το l₁ αντίστοιχα,και ότι περιέχει O(√n) κορυφές, , αντίστοιχα, ειδάλλως θα υπάρξουν περισσότερες από n κορυφές κοντά στα επίπεδα l₁. Δείχνουν ότι πρέπει να υπάρχει ένας διαχωριστής S που σχηματίζεται από την ένωση των l₀ και l₂, τα άκρα του e του ενός άκρου του G που δεν ανήκει στο πρώτο βασικό εύρος αναζήτησης και ότι βρίσκεται μεταξύ των δύο επιπέδων, και οι κορυφές των δυο κατά πλάτος βασικών διαδρομών αναζήτησης από το e μέχρι το επίπεδο l₀. Το μέγεθος του διαχωριστή S κατασκευάστηκε με αυτόν τον τρόπο ώστε να είναι περισσότερο √8√n, ή περίπου 2.83√n. Οι κορυφές του διαχωριστή και των δύο ασυνεχών υπογράφων μπορούν να βρεθούν σε γραμμικό χρόνο.
Αυτή η απόδειξη του θεωρήματος διαχωρισμού ισχύει το ίδιο ικανοποιητικά και σε σταθμισμένα επίπεδα γράφων, στα οποία κάθε κορυφή έχει ένα μη-αρνητικό κόστος. Το γράφημα μπορεί να χωριστεί σε τρεις ομάδες A , S , και Β τέτοια ώστε τα Α και Β να διαθέτουν έκαστος το πολύ τα 2/3 του συνολικού κόστους και το S να έχει O(√n) κορυφές, χωρίς ακμές από το A στο B. Αναλύοντας μια παρόμοια κατασκευή διαχωριστικού πιο προσεκτικά, ο Djidjev (1982) δείχνει ότι το δεσμευμένο με το μέγεθος του S μπορεί να μειωθεί έως √6√n, ή περίπου 2.45√n.
Ο Holzer και άλλοι (2009)) προτείνει μια απλοποιημένη εκδοχή αυτής της προσέγγισης: αυξάνει το γράφημα έτσι ώστε να μεγιστοποιηθεί το επίπεδο και κατασκευάζει ένα εύρος βασικών αναζητήσεων, όπως πριν. Στη συνέχεια, για κάθε ακμή e που δεν αποτελεί μέρος δέντρου(βασικής αναζήτησης), σχηματίζει ένα κύκλο συνδυάζοντας το e με τη διαδρομή του δέντρου που συνδέει τις απολήξεις του. Μπορεί στη συνέχεια να χρησιμοποιήσει ως διαχωριστικό τις κορυφές ενός από αυτούς τους κύκλους. Παρά το γεγονός ότι η προσέγγιση αυτή δεν μπορεί να είναι εγγυημένη για να βρείτε ένα μικρό διαχωρισμό για επίπεδες γραφικές παραστάσεις υψηλής διαμέτρου, τα πειράματα δείχνουν ότι υπερτερεί το εύρος-πρώτες μέθοδοι layering Lipton-Tarjan και Djidjev σε πολλούς τύπους επίπεδων γραφημάτων.

Απλοί διαχωριστές κύκλου

Για ένα γράφημα που είναι ήδη το μέγιστο επίπεδο, μπορεί να παρουσιαστεί μια ισχυρότερη κατασκευή ενός διαχωριστικού κύκλου,έναν κύκλο μικρού μήκους έτσι ώστε το εσωτερικό και το εξωτερικό του κύκλου (στη μοναδική επίπεδη ενσωμάτωση του γραφήματος) να διαθέτουν το καθένα το πολύ 2n/3 κορυφές. Ο Miller (1986) το αποδεικνύει (με το μέγεθος διαχωριστικου του √8√n) χρησιμοποιώντας την τεχνική των Lipton-Tarjan για μια τροποποιημένη έκδοση του πλάτους της πρώτης αναζήτησης στην οποία τα επίπεδα της αναζήτησης σχηματίζουν απλούς κύκλους.
Οι Alon, Seymour & Thomas (1994)αποδεικνύουν την ύπαρξη απλών διαχωριστικών κύκλων πιο άμεσα: ορίζουν C να είναι ένας κύκλος με επι το πλείστον √8√n κορυφές, και με το πολύ 2n/3 εξωτερικές κορυφές του C, τέτοιες που να σχηματίζονται όσο το δυνατόν περισσότερες διαιρέσεις μέσα και έξω από αυτόν, έτσι ώστε να μας δείχνουν ότι οι υποθέσεις αυτές αναγκάζουν τον C να είναι ένας διαχωριστής. Από την άλλη, οι αποστάσεις εντός του Cθα πρέπει να ισούνται με τις αποστάσεις στο δίσκο που περικλείεται από τον C (μια συντομότερη διαδρομή μέσα από το εσωτερικό του δίσκου θα αποτελέσουν μέρος του ορίου ενός καλύτερου κύκλου). Επιπλέον, ο C πρέπει να έχει μήκος ακριβώς √8√n, , όπως αλλιώς θα μπορούσε να βελτιωθεί με την αντικατάσταση ενός από τα άκρα του με τις άλλες δύο πλευρές του τριγώνου. Εάν οι κορυφές του C με αρίθμηση (δεξιόστροφη σειρά) από 1 έως √8√n,και η κορυφή i συνδυάζεται με την κορυφή √8√n − i + 1, τότε αυτά τα συμφωνημένα ζεύγη μπορούν να συνδεθούν με την κορυφή-ασύνδετα μονοπάτια μέσα στον δίσκο, με τη μορφή του του θεωρήματος του Menger για επίπεδες γραφικές παραστάσεις. . Ωστόσο, το συνολικό μήκος των διαδρομών αυτών θα υπερέβαινε κατ 'ανάγκην το n και θα επέφερε μια αντίφαση. Με μια πρόσθετη εργασία δείχνουν με παρόμοια μέθοδο ότι υπάρχει μια απλή μορφή διαχωριστικου κύκλου μεγέθους το πολύ (3/√2)√n, ή περίπου 2.12√n.
Οι Djidjev & Venkatesan (1997) βελτίωσαν περαιτέρω το σταθερό παράγοντα στο απλό θεώρημα του διαχωριστικού κύκλου σε 1.97√n. . Η μέθοδός τους μπορεί επίσης να βρει απλούς διαχωριστικολυς κύκλους για γραφήματα με μη αρνητικά μέτρα κορυφών, με το μέγεθος του διαχωριστή σε περισσότερα 2√n, και μπορεί να παράγει διαχωριστές με μικρότερο μέγεθος σε βάρος μιας πιο άνιση κατάτμηση του γραφήματος. . Σε 2-συνδεδεμένα επίπεδα γραφήματα που δεν είναι μέγιστα, υπάρχουν απλοί διαχωριστικοί κύκλοι με μέγεθος ανάλογο προς την Ευκλείδια νόρμα του διανύσματος των μηκών μορφής που μπορεί να βρεθεί σε σχεδόν γραμμικό χρόνο.

Φασματική στεγανοποίηση

Οι φασματικές μέθοδοι ομαδοποίησης, στις οποίες οι κορυφές ενός γραφήματος ομαδοποιούνται από τις συντεταγμένες των ιδιοδιανύσμάτωνs του matrices που προέρχονται από το γράφημα, χρησιμοποιούνται από καιρό ως ευρετική για τα προβλήματα γραφημάτων διαμέρισης για τα μη επίπεδα γραφήματα. Όπως οι Spielman & Teng (2007) δείχνουν, η φασματική ομαδοποίηση μπορεί επίσης να χρησιμοποιηθεί για να παραγάγει μια εναλλακτική απόδειξη για μια εξασθενημένη μορφή του θεωρήματος διαχωριστικού επιπέδου που ισχύει για επίπεδα γραφήματα με φραγμένο βαθμό. Στη μέθοδο τους, οι κορυφές του δοσμένου επίπεδου γραφήματος ταξινομούνται από τις δεύτερες συντεταγμένες των διοδιανυσμάτων του Laplacian καλουπιού του γραφήματος, και αυτή η ταξινομημένη σειρά κατανέμεται στο σημείο που ελαχιστοποιεί την αναλογία του αριθμού των ακμών που έχουν κοπεί από τη διαμέριση με τον αριθμό των κορυφών για την μικρότερη πλευρά του χωρίσματος. Όπως δείχνουν, κάθε επίπεδη γραφική παράσταση με φραγμένο βαθμό έχει μία διαμέριση αυτού του τύπου στην οποία η αναλογία είναι O(1/√n). Αν και αυτή η κατάτμηση δεν μπορεί να είναι ισορροπημένη, επαναλαμβάνοντας το διαμέρισμα μέσα στο μεγαλύτερο των δύο πλευρών και λαμβάνοντας την ένωση των περικοπών που σχηματίζονται σε κάθε επανάληψη θα οδηγήσει τελικά σε μια ισορροπημένη διαμέριση με O(√n) ακμές. Τα τελικά σημεία αυτών των ακμών σχηματίζουν ένα διαχωριστή μεγέθους O(√n).

Διαχωριστές Ακμών

Μια παραλλαγή του θεωρήματος διαχωριστικού επιπέδου περιλαμβάνει διαχωριστές άκρων,μικρά σύνολα των άκρων σχηματίζουν μία τομή μεταξύ των υποσυνόλων A και B των κορυφών του γραφήματος. Τα δύο σύνολα A και Bπρέπει να έχουν το καθένα μέγεθος το πολύ ένα σταθερό κλάσμα του αριθμού n των κορυφών του γραφήματος (συμβατικά, τα δύο σύνολα έχουν μέγεθος το πολύ 2n/3), και κάθε κορυφή του γραφήματος ανήκει σε ακριβώς ένα από τα A και B. Ο διαχωριστής αποτελείται από τις άκρες που έχουν ένα τελικό σημείο στο A και ένα τελικό σημείο στο B. Φράγματα για το μέγεθος ενός διαχωριστή ακμής περιλαμβάνουν το βαθμό των κορυφών, καθώς και τον αριθμό των κορυφών στο γράφημα: τα επίπεδα γραφήματα στα οποία μία κορυφή έχει βαθμό n − 1, συμπεριλαμβανομένων των τροχιακών γραφικών παραστάσεων s και τον αστεροειδών γραφημάτων, δεν έχουν καμία διαχωριστή άκρη με έναν υπογραμμιστικό αριθμό ακμών, γιατί κάθε διαχωριστή άκρη θα πρέπει να περιλαμβάνει όλες τις ακμές που συνδέουν τον υψηλό βαθμό κορυφών στις κορυφές, από την άλλη πλευρά της τομής. Ωστόσο, κάθε επίπεδη γραφική παράσταση με τη μέγιστο βαθμό Δ έχει διαχωριστή άκρη μεγέθους O(√(Δn)).
Ένας απλός κυκλικός διαχωριστής στο διπλό γράφημα ενός επίπεδου γραφήματος σχηματίζει έναν διαχωριστής άκρης στο αρχικό γράφημα.. Εφαρμόζοντας το απλό διαχωριστικό θεώρημα του κύκλου των Gazit & Miller (1990) στη διπλή γραφική παράσταση ενός δεδομένου γραφήματος επιπέδου ενισχύει το O(√(Δn))όριο για το μέγεθος ενός διαχωριστή άκρης αποδεικνύοντας ότι κάθε επίπεδο γράφημα έχει ένα διαχωριστή άκρης του οποίου το μέγεθος είναι ανάλογο με την Ευκλείδεια νόρμα του διανύσματός των βαθμών της κορυφής.
Οι  περιγράφουν έναν πολυωνυμικό αλγόριθμο για την εύρεση του μικρότερου διαχωριστή άκρης που διαχωρίζει ένα γράφημα G σε δύο υπογραφήματα ίσου μεγέθους, όταν το G είναι ένα υπογράφημα που προκαλείται από ένα γράφημα του δικτύου, χωρίς τρύπες ή με ένα σταθερό αριθμό οπών. Ωστόσο, εικάζουν ότι το πρόβλημα είναι NP-completeγια αυθαίρετα γραφήματα επιπέδου, και δείχνουν ότι η πολυπλοκότητα του προβλήματος είναι η ίδια για γραφήματα πλέγματος με αυθαίρετα πολλές τρύπες, όπως είναι για αυθαίρετα γραφήματα επιπέδου

Κάτω όρια

Σε ένα √n × √n γράφημα πλέγματος, ένα σύνολο S με s < √nσημεία μπορεί να επισυνάψει ένα υποσύνολο το πολύ με s(s − 1)/2 σημεία του πλέγματος, όπου το μέγιστο επιτυγχάνεται με τη διάταξη του S σε μια διαγώνια γραμμή κοντά σε μια γωνιά του πλέγματος. Ως εκ τούτου, προκειμένου να σχηματιστεί ένας διαχωριστής που διαχωρίζει τουλάχιστον n/3 από τα σημεία από το υπόλοιπο δίκτυο, το s πρέπει να είναι τουλάχιστον √(2n/3), δηλαδή περίπου 0.82√n.
Υπάρχουν n-επίπεδων γράφων (για αυθαίρετα μεγάλες τιμές του n) τέτοιες ώστε, για κάθε διαχωριστή S που διαχωρίζει το υπόλοιπο γράφημα σε υπογραφήματα που αποτελούνται από το πολύ 2n/3 κορυφές, το S έχει τουλάχιστον √(4π√3)√n κορυφές, περίπου 1.56√n. Η κατασκευή περιλαμβάνει την προσέγγιση μιας σφαίρας από ένα κυρτό πολύεδρο, αντικαθιστώντας κάθε μία από τις όψεις του πολυέδρου με ένα τριγωνικό πλέγμα, και εφαρμόζοντας ισοπεριμετρικά θεωρήματα s για την επιφάνεια της σφαίρας.

Διαχωριστές Ιεραρχίες

Οι διαχωριστές μπορούν να συνδυάζονται σε μια διαχωριστή ιεραρχία ενός επίπεδου γραφήματος, ενώ μία επαναληπτική αποσύνθεση σε μικρότερα γραφήματα. Μια διαχωριστή ιεραρχία μπορεί να αντιπροσωπεύεται από ένα δυαδικό δένδρο στο οποίο ο κόμβος ρίζα αντιπροσωπεύει την ίδια δεδομένη γραφική παράσταση, και τα δύο παιδιά της ρίζας είναι οι ρίζες των αναδρομικά κατασκευασμένων διαχωριστών ιεραρχιών για τα επαγόμενα υπογραφήματα s που σχηματίζονται από τα δύο υποσύνολα A και B του ενός διαχωριστή.
Μια διαχωριστή ιεραρχία αυτού του τύπου αποτελεί τη βάση για μια αποσύνθεση του δέντρου του δεδομένου γραφήματος, στην οποία το σύνολο των κορυφών που σχετίζονται με κάθε κόμβο του δένδρου είναι η ένωση των διαχωριστών στο μονοπάτι από τον κόμβο στη ρίζα του δένδρου. Δεδομένου ότι τα μεγέθη των γραφημάτων μειώνονται από ένα σταθερό παράγοντα σε κάθε επίπεδο του δέντρου, τα ανώτερα όρια για τα μεγέθη των διαχωριστών επίσης να μειώνονται από ένα σταθερό παράγοντα σε κάθε επίπεδο, έτσι ώστε τα μεγέθη των διαχωριστών για αυτές τις διαδρομές προσθέτουν σε μια γεωμετρική σειρά με O(√n). Δηλαδή, ένας διαχωριστής που σχηματίζεται με τον τρόπο αυτό έχει πλάτος O(√n), και μπορεί να χρησιμοποιηθεί για να δείξει ότι κάθε επίπεδη γραφική παράσταση έχει πλάτος δέντρου O(√n).
Κατασκευάζοντας μια διαχωριστή ιεραρχία άμεσα, διασχίζοντας το δυαδικό δέντρο από πάνω προς τα κάτω και εφαρμόζοντας έναν γραμμικού χρόνου αλγόριθμο διαχωριστικού επιπέδου σε κάθε ένα από τα επαγόμενα υπογραφήματα που συνδέονται με κάθε κόμβο του δυαδικού δέντρου, θα λάβει συνολικά O(n log n) χρόνο. Ωστόσο, είναι δυνατό να κατασκευαστεί μια ολόκληρη διαχωριστή ιεραρχία σε γραμμικό χρόνο, χρησιμοποιώντας το εύρος-πρώτη προσέγγιση διαστρωμάτωσης Lipton-Tarjan και με τη χρήση κατάλληλων δομών δεδομένων s για την εκτέλεση του κάθε βήματος διαμέρισης στο γραμμικό χρόνο.
Αν κάποιος σχηματίζει ένα σχετικό είδος της ιεραρχίας με βάση διαχωρισμούς αντί των διαχωριστών, στην οποία τα δύο παιδιά του κόμβου ρίζας είναι οι ρίζες των αναδρομικών κατασκευαστικών ιεραρχιών για τα δύο υπογραφήματα G₁ και G₂ του διαχωρισμού του δεδομένου γραφήματος, τότε η συνολική δομής δημιουργεί έναν κλάδο αποσύνθεσης αντί για δέντρο αποσύνθεσης . Το πλάτος του κάθε διαχωρισμού σε αυτή την αποσύνθεση είναι, και πάλι, οριοθετημένη από το άθροισμα των μεγεθών των διαχωριστών σε μια διαδρομή από οποιοδήποτε κόμβο στη ρίζα της ιεραρχίας, έτσι ώστε κάθε κλάδος-αποσύνθεσης που σχηματίζεται με τον τρόπο αυτό να έχει πλάτος O(√n) και οποιαδήποτε επίπεδη γραφική παράσταση να έχει πλάτος κλάδων O(√n). ). Μολονότι πολλά άλλα προβλήματα συναφή με το στεγανοποιημένο γράφημα είναι NP-πλήρες, ακόμη και για επίπεδα γραφήματα, είναι δυνατό να βρεθεί ένα ελάχιστο πλάτος διακλάδωσης αποσύνθεσης ενός επίπεδου γραφήματος σε πολυωνυμικό χρόνο. .
Με την εφαρμογή των μεθόδων Alon, Seymour & Thomas (1994)πιο άμεσα στην κατασκευή του κλάδου αποσύνθεσης, οι Fomin & Thilikos (2006a) δείχνουν ότι κάθε επίπεδη γραφική παράσταση έχει πλάτος κλάδου το πολύ 2.12√n,με την ίδια σταθερά, όπως και εκείνο στο απλό θεώρημα διαχωριστή κύκλου του Alon et al. Δεδομένου ότι το πλάτος δέντρου κάθε γραφήματος είναι το πολύ τα 3/2 του πλάτους του κάδου του, αυτό δείχνει επίσης ότι οι επίπεδες γραφικές παραστάσεις έχουν πλάτος δέντρου το πολύ 3.18√n.

Άλλες κατηγορίες γραφημάτων

Ορισμένα αραιά γραφήματα s δεν έχουν γραμμικούς διαχωριστές μεγέθους: σε ένα γράφημα επέκτασης, η διαγραφή μέχρι ένα σταθερό κλάσμα των κορυφών εξακολουθεί να αφήνει μόνο μία συνεκτική συνιστώσα .
Ενδεχομένως το αρχαιότερο γνωστό θεώρημα διαχωρισμού είναι αποτέλεσμα της ότι κάθε δέντρο μπορεί να χωριστεί σε υποδένδρα το πολύ 2n/3 κορυφών κάθε μία από την απομάκρυνση μίας μόνο κορυφής vertex. Ειδικότερα, η κορυφή που ελαχιστοποιεί το μέγιστο μέγεθος του συστατικού έχει αυτή την ιδιότητα, γιατί αν δεν το έκανε, στη συνέχεια, ο γείτονάς της στο μοναδικό μεγάλο υποδένδρο θα μπορούσε να αποτελέσει μία ακόμα καλύτερη διαμέριση. Εφαρμόζοντας την ίδια τεχνική σε μία αποσύνθεση δέντρου ενός αυθαίρετου γραφήματος, είναι δυνατόν να δείξουμε ότι κάθε γράφημα έχει ένα διαχωριστή μεγέθους το πολύ ίσο με το το πλάτος του δέντρου του.
Εάν ένα γράφημα G δεν είναι επίπεδο, αλλά μπορεί να ενσωματωθεί σε μια επιφάνεια του γένους g, τότε έχει ένα διαχωριστή με O((gn)1/2) κορυφές. Οι Gilbert, Hutchinson & Tarjan (1984)απέδειξαν αυτό χρησιμοποιώντας μια προσέγγιση παρόμοια με εκείνη των Lipton & Tarjan (1979). Ομαδοποίησαν τις κορυφές του γραφήματος σε πλάτος-πρώτα επίπεδα και βρήκαν δύο επίπεδα η αφαίρεση του οποίου αφήνει πλέον ένα μεγάλο τμήμα που αποτελείται από ένα μικρό αριθμό των επιπέδων. Αυτό το υπόλοιπο συστατικό μπορεί να γίνει επίπεδο με απομάκρυνση ενός αριθμού πλάτος-πρώτα μονοπάτια ανάλογη προς το γένος, μετά την οποία η μέθοδος Lipton-Tarjan μπορεί να εφαρμοστεί στο υπόλοιπο επίπεδο γράφημα. Το αποτέλεσμα προκύπτει από μια προσεκτική εξισορρόπηση του μεγέθους των δύο επιπέδων που απομακρύνθηκαν έναντι του αριθμού των επιπέδων μεταξύ τους. Εάν η ενσωματωμένη γραφική παράσταση δίνεται ως μέρος της εισόδου, το διαχωριστικό της μπορεί να βρεθεί σε γραμμικό χρόνο. . Γραφικές παραστάσεις του γένους g έχουν επίσης διαχωριστές ακμής μεγέθους O((gΔn)1/2).
Γραφήματα φραγμένου γένους αποτελούν ένα παράδειγμα μιας οικογένειας γραφημάτων κλειστών κάτω από την πράξη της λήψης των μικρότερων, και τα θεωρήματα διαχωρισμού ισχύουν επίσης για αυθαίρετα μικρά κλειστά οικογενειακά γραφήματα. Ειδικότερα, αν ένα οικογενειακό γράφημα έχει ένα απαγορευμένο έλασσον με h κορυφές, τότε έχει ένα διαχωριστή με O(h√n) κορυφές, και ένας τέτοιος διαχωριστής μπορεί να βρεθεί σε χρόνο O(n1 + ε) για κάθε ε > 0.
Η μέθοδος κυκλικού διαχωρισμού των Miller και άλλοι (1997) ) γενικεύεται στα γραφήματα οποιουδήποτε συστήματος d-διαστάσεων με την ιδιότητα ότι κάθε σημείο στο χώρο που καλύπτεται από το πολύ κάποιο σταθερό αριθμό k από μπάλες, σε k-πλησιέστερα γειτονικά γραφήματαs σε d διαστάσεις, και τα γραφήματα που προκύπτουν από πλέγματα πεπερασμένων στοιχείων. Οι σφαιρικοί διαχωριστές κατασκευάστηκαν με αυτόν τον τρόπο χωρίζοντας το γράφημα εισόδου σε υπογραφήματα από το πολύ n(d + 1)/(d + 2) κορυφές. Το μέγεθος των διαχωριστών για k-ply μπάλες kγραφημάτων και γραφήματα k-πλησιέστερου γείτονα είναι O(k1/ᵈn1 - 1/ᵈ).

Ακριβής λύση των NP-hard προβλημάτων βελτιστοποίησης

Με τη χρήση δυναμικού προγραμματισμού σε αποσύνθεση δέντρου ή αποσύνθεση τμήματος ενός επίπεδου γραφήματος, πολλά NP-hard προβλήματα βελτιστοποίησης μπορεί να επιλυθούν σε χρόνο που αυξάνεται εκθετικά με √n ή √n log n. Για παράδειγμα, τα όρια αυτής της μορφής είναι γνωστά για την εύρεση μέγιστων ανεξάρτητων συνόλων, Steiner δέντρα, και Hamiltonian κύκλους, και για την επίλυση του προβλήματος του περιπλανώμενου πωλητή για επίπεδες γραφικές παραστάσεις. Παρόμοιες μέθοδοι που περιλαμβάνουν θεωρήματα διαχωρισμού για τις γεωμετρικές γραφικές παραστάσεις μπορούν να χρησιμοποιηθούν για την Ευκλείδεια επίλυση προβλημάτων του περιπλανώμενου πωλητή και Steiner δέντρα προβλήματα κατασκευής του δέντρου στα όρια του χρόνου της ίδιας μορφής.
Για παραμετροποιημένα προβλήματα που παραδέχονται ένα πυρήνα που διατηρεί επιπεδότητα και μειώνει το γράφημα εισόδου σε ένα πυρήνα του μεγέθους γραμμικού στην παράμετρο εισόδου, αυτή η προσέγγιση μπορεί να χρησιμοποιηθεί για το σχεδιασμό σταθερών παραμέτρων προσιτών αλγορίθμων το χρόνο λειτουργίας των οποίων εξαρτάται πολυωνυμικά από το μέγεθος του γραφήματος εισόδου και εκθετικά για √k, όπου k είναι η παράμετρος του αλγορίθμου. Για παράδειγμα, τα χρονο-όρια αυτής της μορφής είναι γνωστά για την εύρεση κορυφαίων καλυμμάτων και κυριαρχούν σύνολα μεγέθους k.

Αλγόριθμοι προσέγγισης

Οι Lipton & Tarjan (1980) ) παρατήρησαν ότι το θεώρημα διαχωρισμού μπορεί να χρησιμοποιηθεί για την απόκτηση πολυωνυμικών συστημάτων προσέγγισης χρόνου για NP-hard προβλήματα βελτιστοποίησης σε επίπεδες γραφικές παραστάσεις, όπως η εύρεση του μέγιστου ανεξάρτητου συνόλου. Συγκεκριμένα, με την περικοπή μιας ιεραρχίας διαχωριστικών στο κατάλληλο επίπεδο, μπορεί κανείς να βρει ένα διαχωριστικό του μεγέθους O (n/√log n) η αφαίρεση του οποίου διαχωρίζει το γράφημα σε υπογραφήματα μεγέθουςc log n, για κάθε σταθερά c. Με το θεώρημα τεσσάρων χρωμάτων, υπάρχει και ένα ανεξάρτητο σύνολο μεγέθους τουλάχιστονn/4, έτσι ώστε οι κόμβοι απομακρύνονται διαμορφώνουν ένα αμελητέο κλάσμα του μέγιστου ανεξάρτητου συνόλου, και τα μέγιστα ανεξάρτητα σύνολα στα υπόλοιπα υπογραφήματα μπορεί να βρεθούν ανεξάρτητα του εκθετικού χρόνου στο μέγεθος τους. Με το συνδυασμό αυτής της προσέγγισης με τις μεταγενέστερες μεθόδους γραμμικού χρόνου για την κατασκευή ιεραρχικού διαχωριστή και με τον πίνακα αναζήτησης για να μοιραστεί τον υπολογισμό των ανεξάρτητων συνόλων μεταξύ ισομορφικά μπορεί να γίνει για την κατασκευή ανεξάρτητων συνόλων κορυφών μεγέθους εντός ενός παράγοντα 1 − O(1/√log n) του βέλτιστου, σε γραμμικό χρόνο. Ωστόσο, για λόγους προσέγγισης ακόμα πιο κοντά στο 1 από αυτόν τον παράγοντα, μια νεότερη προσέγγιση του Baker (1994) (με βάση δέντρο αποσύνθεση, αλλά όχι σε επίπεδο διαχωριστές) παρέχει καλύτερη ανταλλαγές του χρόνου σε σχέση με την ποιότητα προσέγγιση.
Παρόμοια συστήματα προσέγγισης διαχωριστή που βασίζονται έχουν επίσης χρησιμοποιηθεί για την προσέγγιση άλλων σκληρών προβλημάτων, όπως το κάλυμμα κορυφής. Arora και άλλοι (1998) χρησιμοποιούν διαχωριστικά με έναν διαφορετικό τρόπο για να προσεγγίσουν το πρόβλημα του περιοδεύοντος πωλητή για τη συντομότερη διαδρομή για μετρικά σταθμισμένα επίπεδα γραφήματα; Οι αλγόριθμοι τους χρησιμοποιούν δυναμικό προγραμματισμό για να βρουν τη συντομότερη διαδρομή που, σε κάθε επίπεδο της ιεραρχίας διαχωριστή, διασχίζει το διαχωριστικό ενός οριοθετημένου πολλές φορές, και δείχνουν ότι ως διάβαση δεσμεύεται αυξάνει τις εκδρομές κατασκευάστηκε με αυτόν τον τρόπο έχουν μήκη που προσεγγίζουν τη βέλτιστη περιήγηση.

Συμπιεσμένο Γράφημα

Οι διαχωριστές έχουν χρησιμοποιηθεί ως μέρος των αλγορίθμων συμπίεσης δεδομένων για την αναπαράσταση επίπεδων γραφικών παραστάσεων και άλλα διαχωριστικά γραφήματα χρησιμοποιώντας ένα μικρό αριθμό από bits. Η βασική αρχή αυτών των αλγορίθμων είναι να επιλέξουν έναν αριθμόk και επανειλημμένα να υποδιαιρεθεί το συγκεκριμένο επίπεδο γράφημα με διαχωριστικό σε O(n/k) υπογραφήματα μεγέθους το πολύ k, με O(n/√k) κορυφές στα χωρίσματα. Με την κατάλληλη επιλογή τηςk (στη πιο ανάλογη προς το λογάριθμο της n) ο αριθμός των μη-ισομορφικών υπογραφημάτων k-κορυφών επίπεδων είναι σημαντικά μικρότερος από τον αριθμό των υπογραφημάτων στην αποσύνθεση, έτσι ώστε το γράφημα μπορεί να συμπιεστεί με την κατασκευή ενός πίνακα όλες τα πιθανά μη ισομορφικά υπογραφήματα και εκπροσωπούν κάθε υπογράφο στην αποσύνθεση διαχωριστή με το δείκτη του στον πίνακα. Το υπόλοιπο του γραφήματος, που σχηματίζεται από τις κορυφές διαχωριστή, μπορεί να αντιπροσωπεύεται ρητά ή χρησιμοποιώντας μια αναδρομική εκδοχή της ίδιας δομής δεδομένων. Χρησιμοποιώντας αυτή τη μέθοδο, επίπεδες γραφικές παραστάσεις και πολλά άλλα περιορισμένων οικογενειών επίπεδων γραφημάτων μπορούν να κωδικοποιούνται χρησιμοποιώντας έναν αριθμό bits που είναι πληροφορίες-θεωρητικά βέλτιστες: αν υπάρχουνPₙ n-κορυφή γραφήματα στην οικογένεια των γραφημάτων να εκπροσωπούνται, τότε ένα άτομο γράφημα στην οικογένεια μπορεί να αναπαρασταθεί χρησιμοποιώντας μόνο(1 + o(n))log₂Pₙ bits. είναι επίσης δυνατόν να κατασκευασθούν αναπαραστάσεις αυτού του τύπου στην οποία μπορεί κανείς να δοκιμάσει γειτνίασή μεταξύ των κορυφών, τον καθορισμό του βαθμού μιας κορυφής, και οι λίστες γείτονες των κορυφών σε σταθερό χρόνο ανά ερώτημα, αυξάνοντας το πίνακα υπογράφων με πρόσθετες πληροφορίες σε μορφή πίνακα αντιπροσωπεύουν τις απαντήσεις στα ερωτήματα.

Καθολικά γραφήματα

Ένα καθολικό γράφημα για μια οικογένεια F των γραφημάτων είναι ένα γράφημα που περιέχει κάθε μέλος Fως υπογραφήματα. Ο διαχωριστής μπορεί να χρησιμοποιηθεί για να δείξει ότι οι n-κορυφή επίπεδων γραφιμάτων έχουν καθολικά γραφήματα με n κορυφές και O (n3/2) ακμές.
Η κατασκευή περιλαμβάνει μια ενισχυμένη μορφή του θεωρήματος διαχωριστή στην οποία το μέγεθος των τριών υποσυνόλων των κορυφών στο διαχωριστή δεν εξαρτάται από τη δομή γράφημα: υπάρχει ένας αριθμός c, το μέγεθος της οποίας το πολύ σταθερές φορές √n, τέτοια ότι οι κορυφές του κάθε επίπεδου γραφήματοςn-κορυφή επίπεδα γραφήματα μπορεί να χωριστεί σε υποσύνολα A, S, και B, χωρίς ακμές από το A to B, με |S| = c, και με |A| = |B| = (n − c)/2. Αυτό μπορεί να δειχθεί χρησιμοποιώντας την συνήθη μορφή του θεωρήματος διαχωριστή επανειλημμένα για να στεγανοποιήσει το γράφημα μέχρις ότου όλα τα συστατικά του διαμερίσματος μπορεί να διατάσσονται σε δύο υποσύνολα λιγότερα από n/2 και στη συνέχεια κινείται κορυφές από αυτά τα υποσύνολα στον διαχωριστή ως χρειαστεί, έως ότου να έχει το συγκεκριμένο μέγεθος. Μόλις παρουσιάζεται ένα διαχωριστικό θεώρημα του τύπου αυτού, μπορεί να χρησιμοποιηθεί για να παράγουν μια ιεραρχία διαχωριστή για n-κορυφή επίπεδα γραφήματα που και πάλι δεν εξαρτάται από τη δομή γράφημα: το δέντρο-αποσύνθεσης που σχηματίζεται από αυτήν την ιεραρχία έχει πλάτος O(√n) και μπορεί να χρησιμοποιηθεί για οποιαδήποτε επίπεδη γράφημα. Το σύνολο όλων των ζευγών των κορυφών σε αυτό το δέντρο αποσύνθεση που και οι δύο ανήκουν σε έναν κοινό κόμβο του δέντρου-αποσύνθεσης αποτελεί ένα επιπόλαιο τέλειο γράφημα με O(n3/2) των κορυφών που περιέχει κάθε n-επίπεδο κορυφή γράφημα ως υπογράφημα. Μια παρόμοια κατασκευή δείχνει ότι οριοθετούνται βαθμοί επίπεδων γραφημάτων που έχουν καθολικά γραφήματα με O (n log n) ακμές, όπου η σταθερά κρυμμένη στο συμβολισμό O notation O εξαρτάται από το βαθμό που δεσμεύεται. Κάθε καθολικό γράφημα για επίπεδα γραφήματα (ή ακόμα και για τα δέντρα του απεριόριστου βαθμού) πρέπει να έχει Ω(n log n)ακμές, αλλά παραμένει άγνωστο αν αυτό το κατώτερο όριο ή το O (n3/2) άνω φράγμα είναι σφιχτό για καθολικά γραφήματα για αυθαίρετα επίπεδα γραφήματα.