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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Στη θεωρία γραφημάτων, το θεώρημα διαχωριστικού επιπέδου είναι μια μορφή ισοπεριμετρικών ανισοτήτων για επίπεδες γραφικές παραστάσεις, που αναφέρει ότι οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να χωριστεί σε μικρότερα κομμάτια αφαιρώντας ένα μικρό αριθμό κορυφών. Συγκεκριμένα, η απομάκρυνση της O(√n) κορυφής από ένα γράφημα με n-κορυφές (όπου το 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 μπορεί να υποδιαιρεθεί σε δύο άκρο-ασυνεχείς υπογράφους G1 και G2 με τέτοιο τρόπο ώστε και οι δύο υπογράφοι να έχουν τουλάχιστον n/3 κορυφές και είναι τέτοιες ώστε το σημείο τομής των συνόλων κορυφών των δύο υπογράφων έχει O(√n) ) κορυφές σε αυτό. Μια τέτοια διαίρεση είναι γνωστή ως διαχωρισμός.[1] Αν ο διαχωρισμός είναι δεδομένος, τότε η τομή των συνόλων των κορυφών σχηματίζει ένα διαχωριστικό, και οι κορυφές που ανήκουν σε έναν υπογράφο, αλλά όχι η άλλη μορφή των διαχωρισμένων υποσυνόλων που έχουν το πολύ 2n/3 3 κορυφές. Από την άλλη μεριά, εφόσον υπάρχει μια διαίρεση σε τρία σύνολα A, S, και B που πληρούν τις προϋποθέσεις του θεωρήματος διαχωριστικού επιπέδου, τότε μπορεί κάποιος να σχηματίσει ένα διαχωρισμό στον οποίο τα άκρα με ένα τελικό σημείο A να ανήκει στην G1, , οι άκρες με ένα τελικό σημείο στο B να ανήκουν στην G2, και τα υπόλοιπα άκρα (με τα δύο τελικά σημεία S) να κατανεμηθούν αυθαίρετα.

Η σταθερά των 2/3 στη δήλωση του θεωρήματος διαχωριστικού είναι αυθαίρετο και ίσως μπορεί να αντικατασταθεί από οποιοδήποτε άλλο αριθμό στο ανοικτό διάστημα (1/2, 1), χωρίς να αλλάζει τη μορφή του θεωρήματος: μια διαίρεση σε πιο ίσα υποσύνολα μπορεί να ληφθεί από ακόμα λιγότερες διαιρέσεις κατ 'επανάληψη με τη διάσπαση των μεγαλύτερων συνόλων σε άνισες διαμερίσεις που να ομαδοποιούν τα συνδεδεμένα συστατικά που προκύπτουν.[2]

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

Διαχωριστικό επιπέδου για ένα γράφημα πλέγματος.

Σκεφτείτε ένα γράφημα πλέγματος με 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.[3]

Το θεώρημα διαχωριστικού επιπέδου αναφέρει ότι ένα παρόμοιο διαχωριστικό μπορεί να κατασκευαστεί σε οποιαδήποτε επίπεδο γράφημα. Η περίπτωση της αυθαίρετων επίπεδων γραφημάτων διαφέρει από την περίπτωση των γραφημάτων πλέγματος στο ότι ο διαχωριστής έχει μέγεθος O(√n) ), αλλά ίσως μπορεί να είναι μεγαλύτερο από √n, το όριο του μεγέθους των δύο υποσυνόλων A και B (στις πιο κοινές εκδόσεις του θεωρήματος) είναι 2n/3 και όχι n/2, και οι δυο υποομάδες A δεν χρειάζεται από μόνες τους να συγκροτήσουν συνδεδεμένα γραφήματα.

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

Πρώτο-ευρύ layering[Επεξεργασία | επεξεργασία κώδικα]

Οι Lipton & Tarjan (1979) αυξάνουν το δοθέν επίπεδο γράφημα με πρόσθετες ακμές, αν είναι απαραίτητο, έτσι ώστε να επιτυγχάνεται το μέγιστο επίπεδο (κάθε μορφή σε μια επίπεδη ενσωμάτωση είναι ένα τρίγωνο). Στην συνέχεια εκτελούν μια πρώτη αναζήτηση, ριζωμένη σε μια αυθαίρετη κορυφή v, και κατανείμουν τις κορυφές σε επίπεδα ανάλογα με την απόσταση τους από την κορυφή v. Αν το l1 είναι το μεσαίο επίπεδο (δηλαδή το επίπεδο, όπου ο αριθμός των κορυφών σε υψηλότερα και χαμηλότερα επίπεδα είναι και τα δύο το πολύ n/2) τότε πρέπει να υπάρχουν τα επίπεδα l0 και l2 που είναι O(√n) βήματα πάνω και κάτω από το l1 αντίστοιχα,και ότι περιέχει O(√n) κορυφές, , αντίστοιχα, ειδάλλως θα υπάρξουν περισσότερες από n κορυφές κοντά στα επίπεδα l1. Δείχνουν ότι πρέπει να υπάρχει ένας διαχωριστής S που σχηματίζεται από την ένωση των l0 και l2, τα άκρα του e του ενός άκρου του G που δεν ανήκει στο πρώτο βασικό εύρος αναζήτησης και ότι βρίσκεται μεταξύ των δύο επιπέδων, και οι κορυφές των δυο κατά πλάτος βασικών διαδρομών αναζήτησης από το e μέχρι το επίπεδο l0. Το μέγεθος του διαχωριστή S κατασκευάστηκε με αυτόν τον τρόπο ώστε να είναι περισσότερο √8√n, ή περίπου 2.83√n. Οι κορυφές του διαχωριστή και των δύο ασυνεχών υπογράφων μπορούν να βρεθούν σε γραμμικό χρόνο.

Αυτή η απόδειξη του θεωρήματος διαχωρισμού ισχύει το ίδιο ικανοποιητικά και σε σταθμισμένα επίπεδα γράφων, στα οποία κάθε κορυφή έχει ένα μη-αρνητικό κόστος. Το γράφημα μπορεί να χωριστεί σε τρεις ομάδες A , S , και Β τέτοια ώστε τα Α και Β να διαθέτουν έκαστος το πολύ τα 2/3 του συνολικού κόστους και το S να έχει O(√n) κορυφές, χωρίς ακμές από το A στο B.[4] Αναλύοντας μια παρόμοια κατασκευή διαχωριστικού πιο προσεκτικά, ο 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√ni + 1, τότε αυτά τα συμφωνημένα ζεύγη μπορούν να συνδεθούν με την κορυφή-ασύνδετα μονοπάτια μέσα στον δίσκο, με τη μορφή του του θεωρήματος του Menger για επίπεδες γραφικές παραστάσεις. . Ωστόσο, το συνολικό μήκος των διαδρομών αυτών θα υπερέβαινε κατ 'ανάγκην το n και θα επέφερε μια αντίφαση. Με μια πρόσθετη εργασία δείχνουν με παρόμοια μέθοδο ότι υπάρχει μια απλή μορφή διαχωριστικου κύκλου μεγέθους το πολύ (3/√2)√n, ή περίπου 2.12√n.

Οι Djidjev & Venkatesan (1997) βελτίωσαν περαιτέρω το σταθερό παράγοντα στο απλό θεώρημα του διαχωριστικού κύκλου σε 1.97√n. . Η μέθοδός τους μπορεί επίσης να βρει απλούς διαχωριστικολυς κύκλους για γραφήματα με μη αρνητικά μέτρα κορυφών, με το μέγεθος του διαχωριστή σε περισσότερα 2√n, και μπορεί να παράγει διαχωριστές με μικρότερο μέγεθος σε βάρος μιας πιο άνιση κατάτμηση του γραφήματος. . Σε 2-συνδεδεμένα επίπεδα γραφήματα που δεν είναι μέγιστα, υπάρχουν απλοί διαχωριστικοί κύκλοι με μέγεθος ανάλογο προς την Ευκλείδια νόρμα του διανύσματος των μηκών μορφής που μπορεί να βρεθεί σε σχεδόν γραμμικό χρόνο.[5]

Κυκλικοί διαχωριστές[Επεξεργασία | επεξεργασία κώδικα]

Σύμφωνα με την Koebe–Andreev–Thurston circle-packing theorem, οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να εκπροσωπηθεί από ένα σύνολο κυκλικών δίσκων στο επίπεδο με ασύνδετους εσωτερικούς χώρους, έτσι ώστε δύο κορυφές στο γράφημα να είναι παρακείμενες αν και μόνο αν το αντίστοιχο ζεύγος δίσκων είναι αμοιβαία εφαπτόμενο.Όπως δείχνει ο Miller και άλλοι (1997) για μια τέτοια συσκευασία, υπάρχει ένας κύκλος που έχει το πολύ 3n/4 δίσκους που εφάπτονται σε αυτή ή βρίσκονται εντός αυτού, το πολύ 3n/4 δίσκους που εφάπτονται ή βρίσκονται έξω από αυτόν, και ότι διασχίζει O(√n δίσκους).

Για να το αποδείξει αυτό, ο Miller et al., χρησιμοποιεί στερεογραφική προβολή για να χαρτογραφήσει την συσκευασία πάνω στην επιφάνεια μιας μοναδιαίας σφαίρας σε τρεις διαστάσεις. Επιλέγοντας την προβολή προσεκτικά, το κέντρο της σφαίρας μπορεί να γίνει σε ένα κεντρικό σημείο των κέντρων του δίσκου στην επιφάνειά του, έτσι ώστε οποιοδήποτε επίπεδο που διέρχεται από το κέντρο της σφαίρας, να τη διχοτομεί σε δύο μέρη που ο καθένας περιέχει ή διασταυρώνει το πολύ τα 3n/4 των δίσκων. Αν ένα επίπεδο που διέρχεται από το κέντρο επιλέγεται ομοιόμορφα στην τύχη, ένας δίσκος θα διασχισθεί με πιθανότητα ανάλογη προς την ακτίνα του. Ως εκ τούτου, ο αναμενόμενος αριθμός των δίσκων που διασχίζονται είναι ανάλογος με το άθροισμα των ακτίνων των δίσκων. Ωστόσο, το άθροισμα των τετραγώνων των ακτίνων είναι ανάλογο προς την συνολική επιφάνεια των δίσκων, η οποίο είναι τις περισσότερες φορές η συνολική επιφάνεια της μοναδιαίας σφαίρας, μια σταθερά. Ένα επιχείρημα που αφορά την ανισότητα Jensen δείχνει ότι, όταν το άθροισμα των τετραγώνων των μη-αρνητικών πραγματικών αριθμών οριοθετείται από μια σταθερά, το άθροισμα των ίδιων των αριθμών είναι O(√n). Ως εκ τούτου, ο αναμενόμενος αριθμός των δίσκων που διασχίζονται από ένα τυχαίο επίπεδο είναι O(√n) και εκεί υπάρχει ένα επίπεδο που διασχίζει τους περισσότερους από τους δίσκους. Αυτό το επίπεδο τέμνει τη σφαίρα σε έναν μεγάλο κύκλο, το οποίο προβάλλει πάλι κάτω ένα κύκλο στο επίπεδο με τις επιθυμητές ιδιότητες. Οι O(√n) δίσκοι που διασχίζονται από αυτόν τον κύκλο αντιστοιχούν στις κορυφές ενός γραφήματος επίπεδου διαχωριστή που διαχωρίζει τις κορυφές των οποίων δίσκοι είναι στο εσωτερικό του κύκλου από τις κορυφές των οποίων οι δίσκοι είναι έξω από τον κύκλο, το πολύ σε 3n/4 κορυφές σε κάθε ένα από αυτά τα δύο υποσύνολα.[6][7]

Αυτή η μέθοδος οδηγεί σε έναν τυχαιοποιημένο αλγόριθμο που βρίσκει έναν τέτοιο διαχωριστή σε γραμμικό χρόνο,[6] και ένα λιγότερο πρακτικό ντετερμινιστικό αλγόριθμο με τον ίδιο οριακό γραμμικό χρόνο.[8] Με την ανάλυση αυτού του αλγορίθμου προσεκτικά χρησιμοποιώντας γνωστά όρια σχετικά με την συνολική πυκνότητα των συνολική πυκνότητα των κυκλικών στοιβάδωνs, μπορεί να αποδειχθεί για να βρούμε διαχωριστές του μεγέθους κυρίως

[9]

Αν και αυτό το βελτιωμένο διαχωριστικό οριακό μέγεθος έρχεται σε βάρος μιας πιο άνισης- διαμέρισης του γραφήματος, οι Spielman & Teng (1996)υποστηρίζουν ότι παρέχει ένα βελτιωμένο σταθερό παράγοντα στα χρονικά όρια για ένθετη ανατομή σε σύγκριση με τα διαχωριστικά τωνAlon, Seymour & Thomas (1990).Το μέγεθος των διαχωριστών που παράγει μπορεί να βελτιωθεί περαιτέρω, στην πράξη, με τη χρήση μιας ανομοιόμορφης κατανομής των τυχαίων επιπέδων κοπής.[10]

Η στερεογραφική προβολή στο επιχείρημα του Miller et al. μπορεί να αποφευχθεί με την εξέταση του μικρότερου κύκλου που περιέχει ένα σταθερό κλάσμα των κέντρων των δίσκων και στη συνέχεια να το επεκτείνουμε από μια σταθερή που βρίσκεται στο διάστημα [1,2]. Είναι εύκολο να υποστηρίξουμε, όπως στο Miller et al. , ότι οι δίσκοι τέμνουν το διευρυμένο κύκλο σχηματίζουν έναν έγκυρο διαχωριστή, και ότι, όπως ήταν αναμενόμενο, ο διαχωριστής έχει το σωστό μέγεθος. Οι προκύπτουσες σταθερές είναι κάπως χειρότερα.[11]

Φασματική στεγανοποίηση[Επεξεργασία | επεξεργασία κώδικα]

Οι φασματικές μέθοδοι ομαδοποίησης, στις οποίες οι κορυφές ενός γραφήματος ομαδοποιούνται από τις συντεταγμένες των ιδιοδιανύσμάτωνs του matrices που προέρχονται από το γράφημα, χρησιμοποιούνται από καιρό ως ευρετική για τα προβλήματα γραφημάτων διαμέρισης για τα μη επίπεδα γραφήματα.[12] Όπως οι 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)).[13]

Ένας απλός κυκλικός διαχωριστής στο διπλό γράφημα ενός επίπεδου γραφήματος σχηματίζει έναν διαχωριστής άκρης στο αρχικό γράφημα..[14] Εφαρμόζοντας το απλό διαχωριστικό θεώρημα του κύκλου των Gazit & Miller (1990) στη διπλή γραφική παράσταση ενός δεδομένου γραφήματος επιπέδου ενισχύει το O(√(Δn))όριο για το μέγεθος ενός διαχωριστή άκρης αποδεικνύοντας ότι κάθε επίπεδο γράφημα έχει ένα διαχωριστή άκρης του οποίου το μέγεθος είναι ανάλογο με την Ευκλείδεια νόρμα του διανύσματός των βαθμών της κορυφής.

Οι Παπαδημητρίου & Σιδέρη (1996) περιγράφουν έναν πολυωνυμικό αλγόριθμο για την εύρεση του μικρότερου διαχωριστή άκρης που διαχωρίζει ένα γράφημα G σε δύο υπογραφήματα ίσου μεγέθους, όταν το G είναι ένα υπογράφημα που προκαλείται από ένα γράφημα του δικτύου, χωρίς τρύπες ή με ένα σταθερό αριθμό οπών. Ωστόσο, εικάζουν ότι το πρόβλημα είναι NP-completeγια αυθαίρετα γραφήματα επιπέδου, και δείχνουν ότι η πολυπλοκότητα του προβλήματος είναι η ίδια για γραφήματα πλέγματος με αυθαίρετα πολλές τρύπες, όπως είναι για αυθαίρετα γραφήματα επιπέδου

Κάτω όρια[Επεξεργασία | επεξεργασία κώδικα]

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

Σε ένα √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.[2] Η κατασκευή περιλαμβάνει την προσέγγιση μιας σφαίρας από ένα κυρτό πολύεδρο, αντικαθιστώντας κάθε μία από τις όψεις του πολυέδρου με ένα τριγωνικό πλέγμα, και εφαρμόζοντας ισοπεριμετρικά θεωρήματα s για την επιφάνεια της σφαίρας.

Διαχωριστές Ιεραρχίες[Επεξεργασία | επεξεργασία κώδικα]

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

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

Κατασκευάζοντας μια διαχωριστή ιεραρχία άμεσα, διασχίζοντας το δυαδικό δέντρο από πάνω προς τα κάτω και εφαρμόζοντας έναν γραμμικού χρόνου αλγόριθμο διαχωριστικού επιπέδου σε κάθε ένα από τα επαγόμενα υπογραφήματα που συνδέονται με κάθε κόμβο του δυαδικού δέντρου, θα λάβει συνολικά O(n log n) χρόνο. Ωστόσο, είναι δυνατό να κατασκευαστεί μια ολόκληρη διαχωριστή ιεραρχία σε γραμμικό χρόνο, χρησιμοποιώντας το εύρος-πρώτη προσέγγιση διαστρωμάτωσης Lipton-Tarjan και με τη χρήση κατάλληλων δομών δεδομένων s για την εκτέλεση του κάθε βήματος διαμέρισης στο γραμμικό χρόνο.[15]

Αν κάποιος σχηματίζει ένα σχετικό είδος της ιεραρχίας με βάση διαχωρισμούς αντί των διαχωριστών, στην οποία τα δύο παιδιά του κόμβου ρίζας είναι οι ρίζες των αναδρομικών κατασκευαστικών ιεραρχιών για τα δύο υπογραφήματα G1 και G2 του διαχωρισμού του δεδομένου γραφήματος, τότε η συνολική δομής δημιουργεί έναν κλάδο αποσύνθεσης αντί για δέντρο αποσύνθεσης . Το πλάτος του κάθε διαχωρισμού σε αυτή την αποσύνθεση είναι, και πάλι, οριοθετημένη από το άθροισμα των μεγεθών των διαχωριστών σε μια διαδρομή από οποιοδήποτε κόμβο στη ρίζα της ιεραρχίας, έτσι ώστε κάθε κλάδος-αποσύνθεσης που σχηματίζεται με τον τρόπο αυτό να έχει πλάτος O(√n) και οποιαδήποτε επίπεδη γραφική παράσταση να έχει πλάτος κλάδων O(√n). ). Μολονότι πολλά άλλα προβλήματα συναφή με το στεγανοποιημένο γράφημα είναι NP-πλήρες, ακόμη και για επίπεδα γραφήματα, είναι δυνατό να βρεθεί ένα ελάχιστο πλάτος διακλάδωσης αποσύνθεσης ενός επίπεδου γραφήματος σε πολυωνυμικό χρόνο. .[16]

Με την εφαρμογή των μεθόδων Alon, Seymour & Thomas (1994)πιο άμεσα στην κατασκευή του κλάδου αποσύνθεσης, οι Fomin & Thilikos (2006a) δείχνουν ότι κάθε επίπεδη γραφική παράσταση έχει πλάτος κλάδου το πολύ 2.12√n,με την ίδια σταθερά, όπως και εκείνο στο απλό θεώρημα διαχωριστή κύκλου του Alon et al. Δεδομένου ότι το πλάτος δέντρου κάθε γραφήματος είναι το πολύ τα 3/2 του πλάτους του κάδου του, αυτό δείχνει επίσης ότι οι επίπεδες γραφικές παραστάσεις έχουν πλάτος δέντρου το πολύ 3.18√n.

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

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

Ενδεχομένως το αρχαιότερο γνωστό θεώρημα διαχωρισμού είναι αποτέλεσμα της ότι κάθε δέντρο μπορεί να χωριστεί σε υποδένδρα το πολύ 2n/3 κορυφών κάθε μία από την απομάκρυνση μίας μόνο κορυφής vertex.[6] Ειδικότερα, η κορυφή που ελαχιστοποιεί το μέγιστο μέγεθος του συστατικού έχει αυτή την ιδιότητα, γιατί αν δεν το έκανε, στη συνέχεια, ο γείτονάς της στο μοναδικό μεγάλο υποδένδρο θα μπορούσε να αποτελέσει μία ακόμα καλύτερη διαμέριση. Εφαρμόζοντας την ίδια τεχνική σε μία αποσύνθεση δέντρου ενός αυθαίρετου γραφήματος, είναι δυνατόν να δείξουμε ότι κάθε γράφημα έχει ένα διαχωριστή μεγέθους το πολύ ίσο με το το πλάτος του δέντρου του.

Εάν ένα γράφημα G δεν είναι επίπεδο, αλλά μπορεί να ενσωματωθεί σε μια επιφάνεια του γένους g, τότε έχει ένα διαχωριστή με O((gn)1/2) κορυφές. Οι Gilbert, Hutchinson & Tarjan (1984)απέδειξαν αυτό χρησιμοποιώντας μια προσέγγιση παρόμοια με εκείνη των Lipton & Tarjan (1979). Ομαδοποίησαν τις κορυφές του γραφήματος σε πλάτος-πρώτα επίπεδα και βρήκαν δύο επίπεδα η αφαίρεση του οποίου αφήνει πλέον ένα μεγάλο τμήμα που αποτελείται από ένα μικρό αριθμό των επιπέδων. Αυτό το υπόλοιπο συστατικό μπορεί να γίνει επίπεδο με απομάκρυνση ενός αριθμού πλάτος-πρώτα μονοπάτια ανάλογη προς το γένος, μετά την οποία η μέθοδος Lipton-Tarjan μπορεί να εφαρμοστεί στο υπόλοιπο επίπεδο γράφημα. Το αποτέλεσμα προκύπτει από μια προσεκτική εξισορρόπηση του μεγέθους των δύο επιπέδων που απομακρύνθηκαν έναντι του αριθμού των επιπέδων μεταξύ τους. Εάν η ενσωματωμένη γραφική παράσταση δίνεται ως μέρος της εισόδου, το διαχωριστικό της μπορεί να βρεθεί σε γραμμικό χρόνο. . Γραφικές παραστάσεις του γένους g έχουν επίσης διαχωριστές ακμής μεγέθους O((gΔn)1/2).[18]

Γραφήματα φραγμένου γένους αποτελούν ένα παράδειγμα μιας οικογένειας γραφημάτων κλειστών κάτω από την πράξη της λήψης των μικρότερων, και τα θεωρήματα διαχωρισμού ισχύουν επίσης για αυθαίρετα μικρά κλειστά οικογενειακά γραφήματα. Ειδικότερα, αν ένα οικογενειακό γράφημα έχει ένα απαγορευμένο έλασσον με h κορυφές, τότε έχει ένα διαχωριστή με O(hn) κορυφές, και ένας τέτοιος διαχωριστής μπορεί να βρεθεί σε χρόνο O(n1 + ε) για κάθε ε > 0.[19]

Ένα γράφημα τομής των δίσκων, με το πολύ k = 5 δίσκους που καλύπτουν κάθε σημείο του επιπέδου.

Η μέθοδος κυκλικού διαχωρισμού των Miller και άλλοι (1997) ) γενικεύεται στα γραφήματα οποιουδήποτε συστήματος d-διαστάσεων με την ιδιότητα ότι κάθε σημείο στο χώρο που καλύπτεται από το πολύ κάποιο σταθερό αριθμό k από μπάλες, σε k-πλησιέστερα γειτονικά γραφήματαs σε d διαστάσεις,[6] και τα γραφήματα που προκύπτουν από πλέγματα πεπερασμένων στοιχείων.[20] Οι σφαιρικοί διαχωριστές κατασκευάστηκαν με αυτόν τον τρόπο χωρίζοντας το γράφημα εισόδου σε υπογραφήματα από το πολύ n(d + 1)/(d + 2) κορυφές. Το μέγεθος των διαχωριστών για k-ply μπάλες kγραφημάτων και γραφήματα k-πλησιέστερου γείτονα είναι O(k1/dn1 − 1/d).[6]

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

Αλγόριθμοι διαίρει και βασίλευε[Επεξεργασία | επεξεργασία κώδικα]

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

  • Κατανέμουμε το δεδομένο γράφημα G σε τρία υποσύνολα S, A, B σύμφωνα με το θεώρημα διαχωριστικού επιπέδου
  • Αναδρομική αναζήτηση για τους συντομότερους κύκλους στα A και B
  • Χρησιμοποιούμε τον αλγόριθμο του Dijkstra για να βρούμε, για κάθε s στο S, το συντομότερο κύκλο μέσω s στο G.
  • Επιστρέφουμε το συντομότερο κύκλο που βρέθηκε από τα παραπάνω βήματα.

Ο χρόνος για τις δύο αναδρομικές κλήσεις σε A και Bσε αυτόν τον αλγόριθμο υπερισχύει από το χρόνο για να εκτελέσει το Ο (√n) να καλέσει τον αλγόριθμο του Dijkstra, έτσι ώστε ο αλγόριθμος να βρει το συντομότερο κύκλο σε Ο (n3/2 log n) χρόνο.

Ο ταχύτερος αλγόριθμος για το ίδιο πρόβλημα εύρεσης του συντομότερου κύκλου, που τρέχει σε χρόνο O(n log3n), δόθηκε από τον Wulff-Nilsen (2009). ). Ο αλγόριθμος του χρησιμοποιεί την ίδια διαίρει και βασίλευε διαχωριστική δομή , αλλά χρησιμοποιεί απλό διαχωριστικό κύκλο αντί των τυχαίων διαχωριστικών, έτσι ώστε οι κορυφές τουS να ανήκουν σε μια και μόνο όψη των γραφημάτων μέσα και έξω από το διαχωριστικό του κύκλου. Στη συνέχεια, όταν αντικαθιστά το O(√n) διαχωριστή καλεί τον αλγόριθμο του Dijkstra με πιο πολύπλοκους αλγόριθμους για να βρει τις συντομότερες διαδρομές από όλες τις κορυφές σε μια μόνο όψη ενός επίπεδου γραφήματος και να συνδυάσει τις αποστάσεις από τα δύο υπογραφήματα. Για σταθμισμένα αλλά χωρίς διεύθυνση επίπεδα γραφήματα, ο συντομότερος κύκλος είναι ισοδύναμος με την ελάχιστη μείωση του δυϊκού και μπορεί να βρεθεί σε Ο (n log log n) χρόνο,[21] και ο μικρότερος κύκλος σε ένα μη σταθμισμένο και χωρίς διεύθυνση επίπεδο γράφημα (περίμετρος του) μπορεί να βρεθεί σε χρόνο O(n).[22] (Ωστόσο, ο ταχύτερος αλγόριθμος για μη σταθμισμένα γραφήματα δεν βασίζεται στο θεώρημα διαχωρισμού.)

Ο Frederickson πρότεινε έναν άλλον ταχύτερο αλγόριθμο για μοναδική πηγή συντομότερων διαδρομών με την εφαρμογή του διαχωριστικού θεωρήματος επίπεδων γραφημάτων το 1986.[23] Πρόκειται για μια βελτίωση του αλγορίθμου του Dijkstra με επαναληπτική αναζήτηση σε ένα προσεκτικά επιλεγμένο υποσύνολο των κορυφών.. Αυτή η έκδοση παίρνει Ο (n √(log n)) χρόνο σε ένα γράφημα n-κορυφών. Οι διαχωριστές χρησιμοποιούνται για να βρουν ένα τμήμα ενός γραφήματος, δηλαδή, ένα διαχωρισμό στις ακραίες περιοχές σε δύο ή περισσότερα υποσύνολα, που ονομάζεται περιοχή. Ένας κόμβος λέγεται ότι πρέπει να περιέχονται σε μια περιοχή αν κάποια ακμή της περιοχής προσπίπτει στον κόμβο. Ένας κόμβος που περιέχεται σε περισσότερες από μία περιοχές ονομάζεται όριο κόμβων των περιοχών που το περιέχουν. Η μέθοδος χρησιμοποιεί την έννοια της r-διαίρεσης ενός n-κόμβων γραφημάτων που είναι ένα τμήμα γραφήματος σε Ο (n/r) περιφέρειες, που το καθένα περιέχει (r) κόμβους, συμπεριλαμβανομένων Ο (√r) boundary nodes.) όριο κόμβων. Ο Frederickson έδειξε ότι μια r-διαίρεση μπορεί να βρεθεί σε Ο (n log n) χρόνο με επαναλαμβανόμενη εφαρμογή του διαχωριστικού θεωρήματος.

Το σκίτσο του αλγορίθμου για να λύσει το πρόβλημα του είναι ως εξής.

1.Φάση προεπεξεργασίας: Κατανέμουμε το γράφημα σε προσεκτικές επιλεγμένες υποομάδες κορυφών και καθορίζουμε τις συντομότερες διαδρομές μεταξύ όλων των ζευγών των κορυφών σε αυτές τις υποομάδες, όπου οι ενδιάμεσες κορυφές σε αυτή τη διαδρομή δεν είναι το υποσύνολο. Η φάση αυτή απαιτεί ένα επίπεδο γράφημαG0 να μετατραπεί σε G χωρίς κορυφή έχοντας βαθμό μεγαλύτερο του 3.Από απόρροια του τύπου του Euler ο αριθμός των κορυφών του γραφήματος που προκύπτει θα είναι n ≤ 6n0 -12, όπου n0  είναι ο αριθμός των κορυφών του G0 . Αυτή η φάση εξασφαλίζει επίσης τις ακόλουθες ιδιότητες μιας κατάλληλης r-διαίρεσης.Μια κατάλληλη r-διαίρεση ενός επίπεδου γραφήματος είναι μια r-διαίρεση, έτσι ώστε,

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

2. Φάση Αναζήτησης:

  • Κύρια ώθηση: Βρείτε Μικρότερες αποστάσεις από την πηγή σε κάθε κορυφή στο υποσύνολο. Όταν μια κορυφήvστο υποσύνολο είναι κλειστή, d(w)πρέπει να ενημερώνονται για όλες τις κορυφές w στο υποσύνολο, ότι υπάρχει μια διαδρομή από v στο w.
  • Ολοκληρώνοντας: Καθορίστε τη μικρότερη απόσταση σε κάθε υπόλοιπη κορυφή.

Henzinger et. al. επέκτεινε την τεχνικήr-διαίρεσης Frederickson για την πηγή συντομότερου αλγόριθμου απλής διαδρομής σε επίπεδες γραφικές παραστάσεις για μη αρνητική άκρη μήκη και πρότεινε ένα γραμμικό αλγόριθμο.[24] Η μέθοδός τους γενικεύει την έννοια του γραφήματος Frederickson σε κλάδους, έτσι ώστε τώρα μια (r,s)-- διαίρεση ενός γραφήματος n κόμβων είναι μια διαίρεση σε Ο nτων περιφερειών, που το καθένα περιέχει r{O(1)}  )} κόμβους, που ο καθένας έχει το πολύ s όριο κόμβων. Εάν μια (r, s)-διαίρεση διαιρείται επανειλημμένα σε μικρότερες περιοχές, καλείται να πάρει μια αναδρομική διαίρεση. Αυτός ο αλγόριθμος χρησιμοποιεί περίπου log*n επίπεδα των διαιρέσεων. Η αναδρομική διαίρεση αντιπροσωπεύεται από ένα δέντρο με ρίζα τα φύλλα του οποίου επισημαίνονται με ξεχωριστή ακμή του G. Η ρίζα του δέντρου αντιπροσωπεύει την περιοχή που αποτελείται από πλήρης-G, τα παιδιά της ρίζας αντιπροσωπεύουν τις υποπεριοχές εντός του οποίου αυτή η περιοχή διαιρείται και ούτω καθεξής. Κάθε φύλλο (ατομική περιοχή) αντιπροσωπεύει μια περιοχή που περιέχει ακριβώς μία ακμή. Ένθετη ανατομή είναι ένας διαχωριστής που βασίζεται στη διαίρει και βασιλεύει παραλλαγή της απαλοιφής Gauss για την επίλυση αραιών συμμετρικών συστημάτων γραμμικών εξισώσεωνμε επίπεδη δομή γραφήματος, όπως αυτά προκύπτουν από την μέθοδο των πεπερασμένων στοιχείων. Περιλαμβάνει την εύρεση ενός διαχωριστή για τη γραφική παράσταση που περιγράφει το σύστημα εξισώσεων, αναδρομικά εξαλείφοντας τις μεταβλητές στα δύο υποπροβλήματα διαχωρίζονται από το άλλο με τον διαχωριστή, και στη συνέχεια εξάλειψη των μεταβλητών του διαχωριστή.[3] Το υλικό συμπλήρωσης αυτής της μεθόδου (ο αριθμός των μη μηδενικών συντελεστών που προκύπτει από την διάσπαση Cholesky του πίνακα) είναι Ο (n log n),[25] που επιτρέπει τη μέθοδο αυτή να είναι ανταγωνιστική με επαναληπτικές μεθόδους για τα ίδια προβλήματα.[3]

Οι Klein, Mozes και Weimann [26] έδωσαν έναν Ο (n log2 n)-χρόνο, αλγόριθμος γραμμικού χώρου για να βρουν τη συντομότερη διαδρομή από αποστάσεις s s σε όλους τους κόμβους για ένα κατευθυνόμενο επίπεδο γράφημα με θετικά και αρνητικά τόξα μήκη δεν περιέχουν αρνητικούς κύκλους . Ο αλγόριθμός τους χρησιμοποιεί επίπεδα διαχωριστικά γραφήματα για να βρουν μια Jordan καμπύλη Cπου περνά μέσα από Ο O(√n) κόμβους (και όχι τόξα), έτσι ώστε οι κόμβοι μεταξύ n/3 και 2n/3 να περικλείεται από C. . Κόμβοι μέσω των οποίων διέρχεται η Cείναι όριο κόμβοι.Το αρχικό γράφημα G χωρίζεται σε δύο υπογραφήματα G0  και G1  by cutting the planar embedding along C κόβοντας το ενσωματωμένο επίπεδο κατά μήκος Για i = 0 και 1, σε Gi  οι οριακοί κόμβοι βρίσκονται στο σύνορο μιας ενιαίας όψηςFi .

Η επισκόπηση της προσέγγισης τους δίνεται παρακάτω.

  • Αναδρομικό κάλεσμα: Το πρώτο στάδιο υπολογίζει αναδρομικά τις αποστάσεις από το r κατα Gi  για i = 0, 1.
  • Ενδο -μέρος όριο αποστάσεις: Για κάθε γράφημα G i  υπολογίζουμε όλες τις αποστάσεις μεταξύ των ορίωνGi κόμβων.Αυτό παίρνει O(n log n) χρόνο.
  • Ενιαία-πηγή μεταξύ των τμημάτων όρια αποστάσεων: Μια συντομότερη διαδρομή στο G περνάει μπροστά και πίσω μεταξύ G0  και G1  για τον υπολογισμό των αποστάσεων από G σε r σε όλους τους όριο κόμβους. Εναλλασσόμενες επαναλήψεις χρησιμοποιούν όλες οι οριακές-αποστάσεις $G0  και $G1 . Ο αριθμός των επαναλήψεων είναι Ο (√n),έτσι ώστε ο συνολικός χρόνος για αυτό το στάδιο είναι Ο (n α(n)) όπου α (n) είναι η αντίστροφη συνάρτηση Ackerman.
  • Μία μόνο πηγή αποστάσεων μεταξύ των τμημάτων: Οι αποστάσεις υπολογίζονται στα προηγούμενα στάδια χρησιμοποιούνται, μαζί με έναν υπολογισμό Dijkstra εντός μιας τροποποιημένης έκδοσης του κάθε Gi , για να υπολογίσει τις αποστάσεις στο G από r σε όλους τους κόμβους. Αυτό το στάδιο διαρκεί Ο (n log n) χρόνο.
  • Εκρίζωση αποστάσεων ενιαία πηγή: Οι αποστάσεις από το r σε Gμετατρέπονται σε μη αρνητικά μήκη, και πάλι ο αλγόριθμος του Dijkstra χρησιμοποιείται για τον υπολογισμό αποστάσεων από το s. Το στάδιο αυτό απαιτεί Ο (n log n) χρόνο.

Ένα σημαντικό μέρος αυτού του αλγορίθμου είναι η χρήση των συναρτήσεων και σε μειωμένη τιμή μήκη. Για ένα κατευθυνόμενο γράφημα G με τόξο μήκη ι(·),μια συνάρτηση των τιμών είναι μια συνάρτηση φ από τους κόμβους του G στους πραγματικούς αριθμούς. Για μια uv,τόξου, το μειωμένο μήκος σε σχέση με φ είναι ιφ(uv) = ι(uv) + φ(u) − φ(v). Μια εφικτή τιμή της συνάρτησης είναι συνάρτηση των τιμών που προκαλεί μη αρνητική μείωση σε όλα τα μήκη των τόξων τουG. Είναι χρήσιμο για τη μετατροπή ενός προβλήματος συντομότερης διαδρομής που περιλαμβάνει θετικά και αρνητικά μήκη σε ένα εκ των οποίων περιλαμβάνει μόνο μη αρνητικά μήκη, τα οποία μπορούν στη συνέχεια να λυθούν χρησιμοποιώντας τον αλγόριθμο του Dijkstra.

Το χάσμα διαχωρισμού με βάση το διαίρει και βασίλευε μοντέλο έχει επίσης χρησιμοποιηθεί για το σχεδιασμό δομών δεδομένων για τους δυναμικούς γραφικούς αλγόριθμους[27] και τη θέση του σημείου,[28] αλγόριθμοι για το πολύγωνο τριγωνισμού,[15] συντομότερες διαδρομές s,[29] aκαι την κατασκευή του πλησιέστερου γείτονα γραφήματος ,[30] και η προσέγγιση αλγορίθμων για το μέγιστο ανεξάρτητο σύνολο ενός επίπεδου γραφήματος.[28]

Ακριβής λύση των NP-hard προβλημάτων βελτιστοποίησης[Επεξεργασία | επεξεργασία κώδικα]

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

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

Αλγόριθμοι προσέγγισης[Επεξεργασία | επεξεργασία κώδικα]

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

Παρόμοια συστήματα προσέγγισης διαχωριστή που βασίζονται έχουν επίσης χρησιμοποιηθεί για την προσέγγιση άλλων σκληρών προβλημάτων, όπως το κάλυμμα κορυφής.[34] Arora και άλλοι (1998) χρησιμοποιούν διαχωριστικά με έναν διαφορετικό τρόπο για να προσεγγίσουν το πρόβλημα του περιοδεύοντος πωλητή για τη συντομότερη διαδρομή για μετρικά σταθμισμένα επίπεδα γραφήματα; Οι αλγόριθμοι τους χρησιμοποιούν δυναμικό προγραμματισμό για να βρουν τη συντομότερη διαδρομή που, σε κάθε επίπεδο της ιεραρχίας διαχωριστή, διασχίζει το διαχωριστικό ενός οριοθετημένου πολλές φορές, και δείχνουν ότι ως διάβαση δεσμεύεται αυξάνει τις εκδρομές κατασκευάστηκε με αυτόν τον τρόπο έχουν μήκη που προσεγγίζουν τη βέλτιστη περιήγηση.

Συμπιεσμένο Γράφημα[Επεξεργασία | επεξεργασία κώδικα]

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

Καθολικά γραφήματα[Επεξεργασία | επεξεργασία κώδικα]

Ένα καθολικό γράφημα για μια οικογένεια F των γραφημάτων είναι ένα γράφημα που περιέχει κάθε μέλος Fως υπογραφήματα. Ο διαχωριστής μπορεί να χρησιμοποιηθεί για να δείξει ότι οι n-κορυφή επίπεδων γραφιμάτων έχουν καθολικά γραφήματα με n κορυφές και Ο (n3/2) ακμές.[38]

Η κατασκευή περιλαμβάνει μια ενισχυμένη μορφή του θεωρήματος διαχωριστή στην οποία το μέγεθος των τριών υποσυνόλων των κορυφών στο διαχωριστή δεν εξαρτάται από τη δομή γράφημα: υπάρχει ένας αριθμός 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-επίπεδο κορυφή γράφημα ως υπογράφημα. Μια παρόμοια κατασκευή δείχνει ότι οριοθετούνται βαθμοί επίπεδων γραφημάτων που έχουν καθολικά γραφήματα με Ο (n log n) ακμές, όπου η σταθερά κρυμμένη στο συμβολισμό Ο notation Ο εξαρτάται από το βαθμό που δεσμεύεται. Κάθε καθολικό γράφημα για επίπεδα γραφήματα (ή ακόμα και για τα δέντρα του απεριόριστου βαθμού) πρέπει να έχει Ω(n log n)ακμές, αλλά παραμένει άγνωστο αν αυτό το κατώτερο όριο ή το Ο (n3/2) άνω φράγμα είναι σφιχτό για καθολικά γραφήματα για αυθαίρετα επίπεδα γραφήματα.[38]

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Σημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

  1. Alon, Seymour & Thomas (1990).
  2. 2,0 2,1 Djidjev (1982).
  3. 3,0 3,1 3,2 George (1973). Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.
  4. Lipton & Tarjan (1979).
  5. Gazit & Miller (1990).
  6. 6,0 6,1 6,2 6,3 6,4 Miller και άλλοι (1997).
  7. Pach & Agarwal (1995).
  8. Eppstein, Miller & Teng (1995).
  9. Spielman & Teng (1996).
  10. Gremban, Miller & Teng (1997).
  11. Har-Peled (2011).
  12. Donath & Hoffman (1972); Fiedler (1973).
  13. Miller (1986) proved this result for 2-connected planar graphs, and Diks και άλλοι (1993) extended it to all planar graphs.
  14. Miller (1986); Gazit & Miller (1990).
  15. 15,0 15,1 15,2 Goodrich (1995).
  16. Seymour & Thomas (1994).
  17. Lipton & Tarjan (1979); Erdős, Graham & Szemerédi (1976).
  18. Sýkora & Vrt'o (1993).
  19. Kawarabayashi & Reed (2010). For earlier work on separators in minor-closed families see Alon, Seymour & Thomas (1990), Plotkin, Rao & Smith (1994), and Reed & Wood (2009).
  20. Miller και άλλοι (1998).
  21. Łącki & Sankowski (2011).
  22. Chang & Lu (2011).
  23. Greg n. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Computing, pp. 1004-1022, 1987.
  24. Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, \textit{Faster shortest-path algorithms for planar graphs}, Journal of Computer and System Science, Vol. 55, Issue 1, August 1997.
  25. Lipton, Rose & Tarjan (1979); Gilbert & Tarjan (1986).
  26. Philip N. Klein, Shay Mozes and Oren Weimann, Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log2  n)-Time Algorithm}, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
  27. Eppstein και άλλοι (1996); Eppstein και άλλοι (1998).
  28. 28,0 28,1 Lipton & Tarjan (1980).
  29. Klein και άλλοι (1994); Tazari & Müller-Hannemann (2009).
  30. Frieze, Miller & Teng (1992).
  31. Bern (1990); Deĭneko, Klinz & Woeginger (2006); Dorn και άλλοι (2005); Lipton & Tarjan (1980).
  32. Smith & Wormald (1998).
  33. Alber, Fernau & Niedermeier (2003); Fomin & Thilikos (2006b).
  34. Bar-Yehuda & Even (1982); Chiba (1981).
  35. He, Kao & Lu (2000).
  36. Blandford, Blellock & Kash (2003).
  37. Blellock & Farzan (2010).
  38. 38,0 38,1 Babai και άλλοι (1982); Bhatt και άλλοι (1989); Chung (1990).

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