cyanic-selkie/wikianc huggingface dataset:
Post-rock
Αρχικά χρησιμοποιόταν για να περιγράψει τον ήχο συγκροτημάτων όπως οι Stereolab, Seefeel, Disco Inferno και Pram αλλά με τον καιρό εξελίχθηκε και έχει καταλήξει να περιγράφει κάθε ορχηστρική μουσική με έντονες επιρροές από το Krautrock, την τζαζ και την electronica, που έχει γραφτεί περίπου από τα μέσα της δεκαετίας του 90 και αργότερα.
Υπέρ Κτησιφώντος περί του στεφάνου
Ιστορικό πλαίσιο
Το 336 π.Χ. ο πολιτικός Κτησιφώντας, ο οποίος ανήκε στον πολιτικό κύκλο του Δημοσθένη, πρότεινε η Αθήνα να τιμήσει τον Δημοσθένη για τις υπηρεσίες του προς την πόλη με ένα χρυσό στεφάνι, σύμφωνα με το έθιμο της εποχής. Ο Δημοσθένης, ως τειχοποιός, είχε επισκευάσει με προσωπικά του έξοδα μέρος των τειχών των Αθηνών. Κατά τον Κτησιφώντα το στεφάνι έπρεπε να δοθεί κατά τη διάρκεια των Μεγάλων Διονυσίων, όταν θα παίζονταν οι τραγωδίες, σε μία στιγμή που θα βρίσκονταν στην πόλη και πολλοί ξένοι θεατές, πέρα από τους Αθηναίους.
Post-rock
Το ξεκίνημα
Από τα πρώτα και σημαντικότερα post-rock συγκροτήματα, είναι οι Tortoise από το Σικάγο. Με την κυκλοφορία του Millions Now Living Will Never Die το 1996 δημιούργησαν μια από τις κυριότερες επιρροές για νεότερες μπάντες όπως οι Do Make Say Think, οι οποίες άρχισαν να δημιουργούν μουσική στο ύφος των Tortoise, ορχηστρικό ροκ με αρκετά στοιχεία τζαζ. Ο ήχος αυτός χαρακτηρίστηκε ως post-rock.
Προς τα τέλη της δεκαετίας του 90, το Σικάγο έγινε ένα κέντρο δημιουργίας post-rock μουσικής και με τη βοήθεια του John McEntire από τους Tortoise, ο οποίος βοήθησε στην παραγωγή αρκετών από τους δίσκους που κυκλοφόρησαν εκείνη την εποχή. Την ίδια εποχή συγκροτήματα όπως οι Mogwai από την Σκωτία και οι Godspeed You! Black Emperor από τον Καναδά (αρχικά Godspeed You Black Emperor!) έγιναν (και είναι μέχρι σήμερα) κάποια από τα συγκροτήματα με τη μεγαλύτερη επίδραση στην post-rock σκηνή. Μέχρι και σήμερα έχουν επηρεάσει πολλά συγκροτήματα με τον ήχο τους.
Σιδηροδρομικός Σταθμός Ζαχλωρούς-Μεγάλου Σπηλαίου
Ο Σιδηροδρομικός Σταθμός Ζαχλωρούς-Μεγάλου Σπηλαίου είναι προαιρετικός σιδηροδρομικός σταθμός του Οδοντωτού Σιδηρόδρομου Διακοπτού-Καλαβρύτων που βρίσκεται στην Κάτω Ζαχλωρού στην Αχαΐα, σε μια ορεινή τοποθεσία πλούσιας φυσικής ομορφιάς, μέσα στο φαράγγι του Βουραϊκού και πλησίον των όχθων του ομώνυμου ποταμού. Ο σταθμός άνοιξε το 1896 και εξυπηρετεί επίσης και τους επισκέπτες της μονής του Μεγάλου Σπηλαίου. Έχει 2 γραμμές, μία βασική πλατφόρμα και μία μικρότερη, που άνοιξε το 2010. Πλέον, η βασική πλατφόρμα και η αντίστοιχη της γραμμή δεν χρησιμοποιούνται επειδή είναι πολύ παλιές.
Post-rock
Το ξεκίνημα
Το εύρος του ήχου που καλύπτει ο όρος post-rock άρχισε να μεγαλώνει με το πέρασμα του χρόνου και κάποια στιγμή κατέληξε να χρησιμοποιείται για κάθε ροκ συγκρότημα που πειραματιζόταν με τον ήχο του, με οποιονδήποτε τρόπο. Αυτό είχε ως αποτέλεσμα αρκετά από τα συγκροτήματα (όπως οι Tortoise και οι Mogwai) που βοήθησαν στην καθιέρωση και στην εξάπλωση αυτού του ήχου να αρνηθούν την post-rock ταμπέλα για τη μουσική τους.
Υπέρ Κτησιφώντος περί του στεφάνου
Ιστορικό πλαίσιο
Η πρόταση έγινε αφορμή να δημιουργηθεί πολιτικό ζήτημα το 330 π.Χ., χωρίς να είναι γνωστό γιατί άργησε έξι χρόνια να εκδικαστεί η υπόθεση. Ο Αισχίνης απάντησε στο Δημοσθένη με τον λόγο Κατά Κτησιφώντος, ο οποίος επίσης έχει διασωθεί.
Post-rock
Το παρόν
Σήμερα, αν και τα περισσότερα από τα συγκροτήματα δεν είναι γνωστά στο ευρύ κοινό, το post-rock συνεχίζει να υπάρχει, κυρίως στην indie (ανεξάρτητη) σκηνή. Σημαντικότεροι εκπρόσωποί της είναι οι Ισλανδοί Sigur Rós, Αμερικάνοι Explosions In The Sky και οι Ιάπωνες Mono (συγκρότημα).
Σιδηροδρομικός Σταθμός Ζαχλωρούς-Μεγάλου Σπηλαίου
Yπηρεσίες
Ζαχλωρού Ζαχλωρού Κατηγορία:Δήμος Καλαβρύτων
Υπέρ Κτησιφώντος περί του στεφάνου
Το περιεχόμενο της ομιλίας
Αρχικά, ο Δημοσθένης έδωσε μια γενική εικόνα της κατάστασης στην Ελλάδα, από τότε που μπήκε ο ίδιος στην πολιτική και περιγράφει τις φάσεις του αγώνα του εναντίον του Φιλίππου. Στη συνέχεια ασχολήθηκε με την Ειρήνη του Φιλοκράτη και κατηγορεί τον Αισχίνη του ρόλου του στις διαπραγματεύσεις και την επικύρωση της ειρήνης. Ακόμη επιτίθεται προσωπικά κατά του Αισχίνη και τον ειρωνεύεται για την καταγωγή του από γονείς χαμηλής τάξης. Προσθέτει ακόμη κατηγορίες για διαφθορά και προδοσία, και αποδίδει την καταστροφή στη Χαιρώνειας στη συμπεριφορά του πολιτικού αντιπάλου του, όταν εκπροσωπούσε την Αθήνα στο συμβούλιο της Αμφικτιονίας. Ο Δημοσθένης υπογραμμίζει ότι μόνο αυτός υπερασπίστηκε ενεργά την προώθησε της συμμαχίας με την Θήβα. Τέλος, υποστηρίζει ότι, αν και η Αθήνα ηττήθηκε, θα ήταν καλύτερα να ηττηθεί σε ένα λαμπρό αγώνα για την ανεξαρτησία, παρά να παραδώσει την κληρονομιά της ελευθερίας.
Post-rock
Ήχος και είδη
Σήμερα ως κλασικός post-rock ήχος θεωρείται μια μίξη ambient, electronica, jazz, κλασικού και rock ήχου. Ένα άλλο χαρακτηριστικό του post-rock είναι οι επαναλαμβανόμενοι ήχοι, με μικρές αλλαγές καθώς το τραγούδι σιγά-σιγά φτάνει στην κορύφωσή του. Συνήθως τα τραγούδια είναι μεγάλα σε διάρκεια και δεν έχουν φωνητικά.
Υπέρ Κτησιφώντος περί του στεφάνου
Το περιεχόμενο της ομιλίας
Ο Δημοσθένης τελικά κέρδισε την υπόθεση με συντριπτική πλειοψηφία. Ως αποτέλεσμα, ο Κτησιφώντας αθωώθηκε ενώ ο Αισχίνης τιμωρήθηκε με πρόστιμο και αναγκάστηκε σε εξορία. Πολλοί ειδικοί έχουν καταλήξει στο συμπέρασμα ότι η ομιλία του Αισχίνη ήταν πολύ εύλογη, αν και δεν ήταν ακλόνητη, από νομική άποψη.
Post-rock
Ήχος και είδη
Κλασικότερο παράδειγμα συγκροτήματος με φωνητικά είναι οι Sigur Rós. Το συγκρότημα έχει φωνητικά στα περισσότερα τραγούδια του, αλλά όλοι οι στίχοι είναι στα ισλανδικά και στα hopelandic (μια γλώσσα που δημιούργησαν οι ίδιοι οι Sigur Rós και δεν έχει συγκεκριμένες λέξεις). Στην ουσία τα φωνητικά απλά ντύνουν την μουσική και χρησιμοποιούνται ως άλλο ένα όργανο.
Υπέρ Κτησιφώντος περί του στεφάνου
Εκτιμήσεις για το έργο
thumb|left|Χειρόγραφο στα λατινικά με τον «Περί στεφάνου» λόγο, Αυστριακή Εθνική Βιβλιοθήκη (Österreichische Nationalbibliothek) cod. 3186 Ο λόγος υπέρ του στεφάνου έχει χαρακτηριστεί «η μεγαλύτερη ομιλία του μεγαλύτερου ρήτορα στον κόσμο» και μια από τις καλύτερες αγορεύσεις πολιτικού περιχομένου Άλλος φιλόλογος, ο Ρ. Κ. Τζεμπ αναλύοντας την ρητορική διαμάχη μεταξύ Δημοσθένη και Αισχίνη, υπογραμμίζει ότι αυτή η έντονη αντιπαράθεση απεικονίζει την τελευταία μεγάλη φάση της πολιτικής ζωής στην Αθήνα. Επισημαίνει ακόμη ότι «η θεωρία της ελληνικής ευγλωττίας είχε τελική και πιο υπέροχη απεικόνισή της σε αυτήν τη δίκη που έφερε στο προσκήνιο τις δύο ομιλίες περί του στεφάνου».
Post-rock
Ήχος και είδη
Συγκροτήματα όπως οι Pelican, οι Isis και οι Red Sparowes έχουν καθιερώσει μια μίξη post-rock και metal δημιουργώντας έτσι πιο σκληρά ορχηστρικά κομμάτια με πολλά από τα στοιχεία του post-rock. Μερικά συγκροτήματα έχουν χρησιμοποιήσει ακόμα και φωνητικά όμοια με αυτά που χρησιμοποιούνται στο ντέθ μέταλ. Από την άλλη μεριά, συγκροτήματα όπως οι 65daysofstatic και οι From Monument To Masses, χρησιμοποιούν samples και άλλα στοιχεία της electronica στη μουσική τους, δημιουργώντας έναν καινούργιο, ξεχωριστό ήχο. Οι Rachel´s, οι Clogs και άλλοι συνδυάζουν το post-rock με την κλασική μουσική, οδηγώντας σε λιγότερο θορυβώδη και με πιο αργό ρυθμό τραγούδια.
Υπέρ Κτησιφώντος περί του στεφάνου
Το απόσπασμα από το έργο
Στο απόσπασμα (από τις παραγράφους 169-172) ο Δημοσθένης περιγράφει με τρόπο γλαφυρό και παραστατικό τη σύγχυση και την ταραχή που επικράτησε στην Αθήνα μετά την αναγγελία της κατάληψης της Ελάτειας από τον Φίλιππο. Ο Πατριάρχης Φώτιος εξαίρει το συγκεκριμένο χωρίο.
Post-rock
Ήχος και είδη
Γενικότερα η post-rock σκηνή είναι έντονα πειραματική, με πολλούς καλλιτέχνες που θέλουν να δοκιμάσουν καινούργια πράγματα, ίσως επειδή η έλλειψη φωνητικών σε πολλές περιπτώσεις κάνει δυσκολότερη την προσπάθεια των συγκροτημάτων να ξεχωρίσουν.
Υπέρ Κτησιφώντος περί του στεφάνου
Εξωτερικοί σύνδεσμοι
Κατηγορία:Δημοσθένης Κατηγορία:Δικανικοί λόγοι
Post-rock
Εξωτερικοί Σύνδεσμοι
To άρθρο του Reynolds To άρθρο για την Post Rock μουσική έννοια από το Postrocking
Κατηγορία:Εναλλακτική ροκ
Θεώρημα διαχωρισμού του επιπέδου
Στη θεωρία γραφημάτων, το θεώρημα διαχωριστικού επιπέδου  είναι μια μορφή ισοπεριμετρικών ανισοτήτων για επίπεδες γραφικές παραστάσεις, που αναφέρει ότι οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να χωριστεί σε μικρότερα κομμάτια αφαιρώντας ένα μικρό αριθμό κορυφών. Συγκεκριμένα, η απομάκρυνση της O(√n) κορυφής από ένα γράφημα με n-κορυφές (όπου το O επικαλείται επικαλείται μεγάλο Ο συμβολισμό) μπορεί να χωρίσει το γράφημα σε ασυνεχείς υπογράφους καθένα από τα οποία έχει το πολύ 2n / 3 κορυφές.
Μια ηπιότερη μορφή του θεωρήματος διαχωρισμού με O(√n log n) κορυφές στο διαχωριστή αντί για O(√n) αρχικά αποδεικνύεται από τον, καθώς και η μορφή με την στενή ασύμπτωτη δεσμεύεται από το μέγεθος της διαχωριστικής που πρωτοαποδείχτηκε από τον. Δεδομένου του έργου τους, το θεώρημα διαχωρισμού έχει αποδειχτεί ξανά με διάφορους τρόπους,ο σταθερός στη θέση 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) ) κορυφές σε αυτό. Μια τέτοια διαίρεση είναι γνωστή ως διαχωρισμός. Αν ο διαχωρισμός είναι δεδομένος, τότε η τομή των συνόλων των  κορυφών  σχηματίζει ένα διαχωριστικό, και οι κορυφές που ανήκουν σε έναν υπογράφο, αλλά όχι η άλλη μορφή των διαχωρισμένων υποσυνόλων που έχουν το πολύ  2n/3 3 κορυφές. Από την άλλη μεριά, εφόσον υπάρχει μια διαίρεση σε τρία σύνολα  A, S, και B που πληρούν τις προϋποθέσεις του θεωρήματος διαχωριστικού επιπέδου, τότε μπορεί κάποιος να σχηματίσει ένα διαχωρισμό στον οποίο τα άκρα με ένα τελικό σημείο A να ανήκει στην G1,, οι άκρες με ένα τελικό σημείο στο  B να ανήκουν στην G2, και τα υπόλοιπα άκρα (με τα δύο τελικά σημεία 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
Οι αυξάνουν το δοθέν επίπεδο γράφημα  με πρόσθετες ακμές, αν είναι απαραίτητο, έτσι ώστε να επιτυγχάνεται το μέγιστο επίπεδο (κάθε μορφή σε μια επίπεδη ενσωμάτωση είναι ένα τρίγωνο). Στην συνέχεια εκτελούν μια πρώτη αναζήτηση, ριζωμένη σε μια αυθαίρετη κορυφή 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. Αναλύοντας μια παρόμοια κατασκευή διαχωριστικού πιο προσεκτικά, ο δείχνει ότι το δεσμευμένο με το μέγεθος του  S μπορεί να μειωθεί έως √6√n, ή περίπου 2.45√n.
Ο ) προτείνει μια απλοποιημένη εκδοχή αυτής της προσέγγισης: αυξάνει το γράφημα έτσι ώστε να μεγιστοποιηθεί το επίπεδο και κατασκευάζει ένα εύρος βασικών αναζητήσεων, όπως πριν. Στη συνέχεια, για κάθε ακμή  e  που δεν αποτελεί μέρος δέντρου(βασικής αναζήτησης), σχηματίζει ένα κύκλο συνδυάζοντας το  e  με τη διαδρομή του δέντρου που συνδέει τις απολήξεις του. Μπορεί στη συνέχεια να χρησιμοποιήσει ως διαχωριστικό τις κορυφές ενός από αυτούς τους κύκλους. Παρά το γεγονός ότι η προσέγγιση αυτή δεν μπορεί να είναι εγγυημένη για να βρείτε ένα μικρό διαχωρισμό για επίπεδες γραφικές παραστάσεις υψηλής διαμέτρου, τα πειράματα δείχνουν ότι υπερτερεί το εύρος-πρώτες μέθοδοι layering Lipton-Tarjan και Djidjev σε πολλούς τύπους επίπεδων γραφημάτων.
Απλοί διαχωριστές κύκλου
Για ένα γράφημα που είναι ήδη το μέγιστο επίπεδο, μπορεί να παρουσιαστεί μια ισχυρότερη κατασκευή ενός  διαχωριστικού κύκλου,έναν κύκλο μικρού μήκους έτσι ώστε το εσωτερικό και το εξωτερικό του κύκλου (στη μοναδική επίπεδη ενσωμάτωση του γραφήματος) να διαθέτουν το καθένα το πολύ 2n/3 κορυφές. Ο το αποδεικνύει (με το μέγεθος διαχωριστικου του √8√n) χρησιμοποιώντας την τεχνική των Lipton-Tarjan για μια τροποποιημένη έκδοση του πλάτους της πρώτης αναζήτησης στην οποία τα επίπεδα της αναζήτησης σχηματίζουν απλούς κύκλους.
Οι αποδεικνύουν την ύπαρξη απλών διαχωριστικών κύκλων πιο άμεσα: ορίζουν 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.
Οι βελτίωσαν  περαιτέρω το σταθερό παράγοντα στο απλό θεώρημα του διαχωριστικού κύκλου σε  1.97√n. . Η μέθοδός τους μπορεί επίσης να βρει απλούς διαχωριστικολυς κύκλους για γραφήματα με μη αρνητικά μέτρα κορυφών, με το μέγεθος του διαχωριστή σε περισσότερα 2√n, και μπορεί να παράγει διαχωριστές με μικρότερο μέγεθος σε βάρος μιας πιο άνιση κατάτμηση του γραφήματος. . Σε 2-συνδεδεμένα επίπεδα γραφήματα που δεν είναι μέγιστα, υπάρχουν απλοί διαχωριστικοί κύκλοι με μέγεθος ανάλογο προς την Ευκλείδια νόρμα του διανύσματος των μηκών μορφής που μπορεί να βρεθεί σε σχεδόν γραμμικό χρόνο.
Κυκλικοί διαχωριστές
Σύμφωνα με την Koebe–Andreev–Thurston circle-packing theorem, οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να εκπροσωπηθεί από ένα σύνολο κυκλικών δίσκων στο επίπεδο με ασύνδετους εσωτερικούς χώρους, έτσι ώστε δύο κορυφές στο γράφημα να είναι παρακείμενες αν και μόνο αν το αντίστοιχο ζεύγος δίσκων είναι αμοιβαία εφαπτόμενο.Όπως δείχνει ο   για μια τέτοια συσκευασία, υπάρχει ένας κύκλος που έχει το πολύ 3n/4 δίσκους που εφάπτονται σε αυτή ή βρίσκονται εντός αυτού, το πολύ 3n/4 δίσκους που εφάπτονται ή βρίσκονται έξω από αυτόν, και ότι διασχίζει O(√n δίσκους).
Για να το αποδείξει αυτό, ο Miller et al., χρησιμοποιεί  στερεογραφική προβολή για να χαρτογραφήσει την συσκευασία πάνω στην επιφάνεια μιας μοναδιαίας σφαίρας σε τρεις διαστάσεις. Επιλέγοντας την προβολή προσεκτικά, το κέντρο της σφαίρας μπορεί να γίνει σε ένα  κεντρικό σημείο των κέντρων του δίσκου στην επιφάνειά του, έτσι ώστε οποιοδήποτε επίπεδο που διέρχεται από το κέντρο της σφαίρας, να τη διχοτομεί σε δύο μέρη που ο καθένας περιέχει ή διασταυρώνει το πολύ τα  3n/4 των δίσκων. Αν ένα επίπεδο που διέρχεται από το κέντρο επιλέγεται ομοιόμορφα στην τύχη, ένας δίσκος θα διασχισθεί με πιθανότητα ανάλογη προς την ακτίνα του. Ως εκ τούτου, ο αναμενόμενος αριθμός των δίσκων που διασχίζονται είναι ανάλογος με το άθροισμα των ακτίνων των δίσκων. Ωστόσο, το άθροισμα των τετραγώνων των ακτίνων είναι ανάλογο προς την συνολική επιφάνεια των δίσκων, η οποίο είναι τις περισσότερες φορές η συνολική επιφάνεια της μοναδιαίας σφαίρας, μια σταθερά. Ένα επιχείρημα που αφορά την ανισότητα Jensen δείχνει ότι, όταν το άθροισμα των τετραγώνων των  μη-αρνητικών πραγματικών αριθμών οριοθετείται από μια σταθερά, το άθροισμα των ίδιων των αριθμών είναι  O(√n). Ως εκ τούτου, ο αναμενόμενος αριθμός των δίσκων που διασχίζονται από ένα τυχαίο επίπεδο είναι O(√n) και εκεί υπάρχει ένα επίπεδο που διασχίζει τους περισσότερους από τους δίσκους. Αυτό το επίπεδο τέμνει τη σφαίρα σε έναν μεγάλο κύκλο, το οποίο προβάλλει πάλι κάτω ένα κύκλο στο επίπεδο με τις επιθυμητές ιδιότητες. Οι O(√n) δίσκοι που διασχίζονται από αυτόν τον κύκλο αντιστοιχούν στις κορυφές ενός γραφήματος επίπεδου διαχωριστή που διαχωρίζει τις κορυφές των οποίων δίσκοι είναι στο εσωτερικό του κύκλου από τις κορυφές των οποίων οι δίσκοι είναι έξω από τον κύκλο, το πολύ σε 3n/4 κορυφές σε κάθε ένα από αυτά τα δύο υποσύνολα.
Αυτή η μέθοδος οδηγεί σε έναν τυχαιοποιημένο αλγόριθμο που βρίσκει έναν τέτοιο διαχωριστή σε  γραμμικό χρόνο, και ένα λιγότερο πρακτικό  ντετερμινιστικό αλγόριθμο με τον ίδιο οριακό γραμμικό χρόνο. Με την ανάλυση αυτού του αλγορίθμου προσεκτικά χρησιμοποιώντας γνωστά όρια σχετικά με την συνολική πυκνότητα των συνολική πυκνότητα των κυκλικών στοιβάδωνs, μπορεί να αποδειχθεί για να βρούμε διαχωριστές του μεγέθους κυρίως Αν και αυτό το βελτιωμένο διαχωριστικό οριακό μέγεθος έρχεται σε βάρος μιας πιο άνισης- διαμέρισης του γραφήματος, οι υποστηρίζουν ότι παρέχει ένα βελτιωμένο σταθερό παράγοντα στα χρονικά όρια για ένθετη ανατομή σε σύγκριση με τα διαχωριστικά των.Το μέγεθος των διαχωριστών που παράγει μπορεί να βελτιωθεί περαιτέρω, στην πράξη, με τη χρήση μιας ανομοιόμορφης κατανομής των τυχαίων επιπέδων κοπής.
Η στερεογραφική προβολή στο επιχείρημα του Miller et al. μπορεί να αποφευχθεί με την εξέταση του μικρότερου κύκλου που περιέχει ένα σταθερό κλάσμα των κέντρων των δίσκων και στη συνέχεια να το επεκτείνουμε από μια σταθερή που βρίσκεται στο διάστημα [1,2]. Είναι εύκολο να υποστηρίξουμε, όπως στο Miller et al., ότι οι δίσκοι τέμνουν το διευρυμένο κύκλο σχηματίζουν έναν έγκυρο διαχωριστή, και ότι, όπως ήταν αναμενόμενο, ο διαχωριστής έχει το σωστό μέγεθος. Οι προκύπτουσες σταθερές είναι κάπως χειρότερα.
Φασματική στεγανοποίηση
Οι φασματικές μέθοδοι ομαδοποίησης, στις οποίες οι κορυφές ενός γραφήματος ομαδοποιούνται από τις συντεταγμένες των ιδιοδιανύσμάτωνs του matrices που προέρχονται από το γράφημα, χρησιμοποιούνται από καιρό ως ευρετική για τα προβλήματα γραφημάτων διαμέρισης για τα μη επίπεδα γραφήματα. Όπως οι δείχνουν, η  φασματική ομαδοποίηση μπορεί επίσης να χρησιμοποιηθεί για να παραγάγει μια εναλλακτική απόδειξη για μια εξασθενημένη μορφή του θεωρήματος διαχωριστικού επιπέδου που ισχύει για επίπεδα γραφήματα με φραγμένο βαθμό. Στη μέθοδο τους, οι κορυφές του δοσμένου επίπεδου γραφήματος ταξινομούνται από τις δεύτερες συντεταγμένες των διοδιανυσμάτων του Laplacian καλουπιού του γραφήματος, και αυτή η ταξινομημένη σειρά κατανέμεται στο σημείο που ελαχιστοποιεί την αναλογία του αριθμού των ακμών που έχουν κοπεί από τη διαμέριση με τον αριθμό των κορυφών για την μικρότερη πλευρά του χωρίσματος. Όπως δείχνουν, κάθε επίπεδη γραφική παράσταση με φραγμένο βαθμό έχει μία διαμέριση αυτού του τύπου στην οποία η αναλογία είναι O(1/√n). Αν και αυτή η κατάτμηση δεν μπορεί να είναι ισορροπημένη, επαναλαμβάνοντας το διαμέρισμα μέσα στο μεγαλύτερο των δύο πλευρών και λαμβάνοντας την ένωση των περικοπών που σχηματίζονται σε κάθε επανάληψη θα οδηγήσει τελικά σε μια ισορροπημένη διαμέριση με O(√n) ακμές. Τα τελικά σημεία αυτών των ακμών σχηματίζουν ένα διαχωριστή μεγέθους O(√n).
Διαχωριστές Ακμών
Μια παραλλαγή του θεωρήματος διαχωριστικού επιπέδου περιλαμβάνει διαχωριστές άκρων,μικρά σύνολα των άκρων σχηματίζουν μία  τομή μεταξύ των υποσυνόλων A και B των κορυφών του γραφήματος. Τα δύο σύνολα A και Bπρέπει να έχουν το καθένα μέγεθος το πολύ ένα σταθερό κλάσμα του αριθμού n των κορυφών του γραφήματος (συμβατικά, τα δύο σύνολα έχουν μέγεθος το πολύ 2n/3), και κάθε κορυφή του γραφήματος ανήκει σε ακριβώς ένα από τα A και B. Ο διαχωριστής αποτελείται από τις άκρες που έχουν ένα τελικό σημείο στο A και ένα τελικό σημείο στο B. Φράγματα για το μέγεθος ενός διαχωριστή ακμής περιλαμβάνουν το βαθμό των κορυφών, καθώς και τον αριθμό των κορυφών στο γράφημα: τα επίπεδα γραφήματα στα οποία μία κορυφή έχει βαθμό n − 1, συμπεριλαμβανομένων των τροχιακών γραφικών παραστάσεων s και τον αστεροειδών γραφημάτων, δεν έχουν καμία διαχωριστή άκρη με έναν υπογραμμιστικό αριθμό ακμών, γιατί κάθε διαχωριστή άκρη θα πρέπει να περιλαμβάνει όλες τις ακμές που συνδέουν τον υψηλό βαθμό κορυφών στις κορυφές, από την άλλη πλευρά της τομής. Ωστόσο, κάθε επίπεδη γραφική παράσταση με τη μέγιστο βαθμό Δ έχει διαχωριστή άκρη μεγέθους O(√(Δn)).
Ένας απλός κυκλικός διαχωριστής στο διπλό γράφημα ενός επίπεδου γραφήματος σχηματίζει έναν διαχωριστής άκρης στο αρχικό γράφημα.. Εφαρμόζοντας το απλό διαχωριστικό θεώρημα του κύκλου των  στη διπλή γραφική παράσταση ενός δεδομένου γραφήματος επιπέδου ενισχύει το  O(√(Δn))όριο για το μέγεθος ενός διαχωριστή άκρης αποδεικνύοντας ότι κάθε επίπεδο γράφημα έχει ένα διαχωριστή άκρης του οποίου το μέγεθος είναι ανάλογο με την Ευκλείδεια νόρμα του διανύσματός των βαθμών της κορυφής.
Οι Παπαδημητρίου & Σιδέρη (1996) περιγράφουν έναν πολυωνυμικό αλγόριθμο για την εύρεση του μικρότερου διαχωριστή άκρης που διαχωρίζει ένα γράφημα 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 για την εκτέλεση του κάθε βήματος διαμέρισης στο γραμμικό χρόνο.
Αν κάποιος σχηματίζει ένα σχετικό είδος της ιεραρχίας με βάση διαχωρισμούς αντί των διαχωριστών, στην οποία τα δύο παιδιά του κόμβου ρίζας είναι οι ρίζες των αναδρομικών κατασκευαστικών ιεραρχιών για τα δύο υπογραφήματα G1 και G2 του διαχωρισμού του δεδομένου γραφήματος, τότε η συνολική δομής δημιουργεί έναν κλάδο αποσύνθεσης αντί για δέντρο αποσύνθεσης. Το πλάτος του κάθε διαχωρισμού σε αυτή την αποσύνθεση είναι, και πάλι, οριοθετημένη από το άθροισμα των μεγεθών των διαχωριστών σε μια διαδρομή από οποιοδήποτε κόμβο στη ρίζα της ιεραρχίας, έτσι ώστε κάθε κλάδος-αποσύνθεσης που σχηματίζεται με τον τρόπο αυτό να έχει πλάτος O(√n) και οποιαδήποτε επίπεδη γραφική παράσταση να έχει πλάτος κλάδων O(√n). ). Μολονότι πολλά άλλα προβλήματα συναφή με το στεγανοποιημένο γράφημα είναι NP-πλήρες, ακόμη και για επίπεδα γραφήματα, είναι δυνατό να βρεθεί ένα ελάχιστο πλάτος διακλάδωσης αποσύνθεσης ενός επίπεδου γραφήματος σε πολυωνυμικό χρόνο..
Με την εφαρμογή των μεθόδων πιο άμεσα στην κατασκευή του κλάδου αποσύνθεσης, οι   δείχνουν ότι κάθε επίπεδη γραφική παράσταση έχει πλάτος κλάδου το πολύ 2.12√n,με την ίδια σταθερά, όπως και εκείνο στο απλό θεώρημα διαχωριστή κύκλου του Alon et al. Δεδομένου ότι το πλάτος δέντρου κάθε γραφήματος είναι το πολύ τα 3/2 του πλάτους του κάδου του, αυτό δείχνει επίσης ότι οι επίπεδες γραφικές παραστάσεις έχουν πλάτος δέντρου το πολύ  3.18√n.
Άλλες κατηγορίες γραφημάτων
Ορισμένα αραιά γραφήματα s δεν έχουν γραμμικούς διαχωριστές μεγέθους: σε ένα γράφημα επέκτασης, η διαγραφή μέχρι ένα σταθερό κλάσμα των κορυφών εξακολουθεί να αφήνει μόνο μία συνεκτική συνιστώσα.
Ενδεχομένως το αρχαιότερο γνωστό θεώρημα διαχωρισμού είναι αποτέλεσμα της ότι κάθε δέντρο μπορεί να χωριστεί σε υποδένδρα το πολύ  2n/3 κορυφών κάθε μία από την απομάκρυνση μίας μόνο κορυφής vertex. Ειδικότερα, η κορυφή που ελαχιστοποιεί το μέγιστο μέγεθος του συστατικού έχει αυτή την ιδιότητα, γιατί αν δεν το έκανε, στη συνέχεια, ο γείτονάς της στο μοναδικό μεγάλο υποδένδρο θα μπορούσε να αποτελέσει μία ακόμα καλύτερη διαμέριση. Εφαρμόζοντας την ίδια τεχνική σε μία αποσύνθεση δέντρου ενός αυθαίρετου γραφήματος, είναι δυνατόν να δείξουμε ότι κάθε γράφημα έχει ένα διαχωριστή μεγέθους το πολύ ίσο με το το πλάτος του δέντρου του.
Εάν ένα γράφημα G δεν είναι επίπεδο, αλλά μπορεί να ενσωματωθεί σε μια επιφάνεια του γένους g, τότε έχει ένα διαχωριστή με  O((gn)1/2) κορυφές. Οι απέδειξαν αυτό χρησιμοποιώντας μια προσέγγιση παρόμοια με εκείνη των. Ομαδοποίησαν τις κορυφές του γραφήματος σε πλάτος-πρώτα επίπεδα και βρήκαν  δύο επίπεδα η αφαίρεση του οποίου αφήνει πλέον ένα μεγάλο τμήμα που αποτελείται από ένα μικρό αριθμό των επιπέδων. Αυτό το υπόλοιπο συστατικό μπορεί να γίνει επίπεδο με απομάκρυνση ενός αριθμού πλάτος-πρώτα μονοπάτια ανάλογη προς το γένος, μετά την οποία η μέθοδος Lipton-Tarjan μπορεί να εφαρμοστεί στο υπόλοιπο επίπεδο γράφημα. Το αποτέλεσμα προκύπτει από μια προσεκτική εξισορρόπηση του μεγέθους των δύο επιπέδων που απομακρύνθηκαν έναντι του αριθμού των επιπέδων μεταξύ τους. Εάν η ενσωματωμένη γραφική παράσταση δίνεται ως μέρος της εισόδου, το διαχωριστικό της μπορεί να βρεθεί σε γραμμικό χρόνο. . Γραφικές παραστάσεις του γένους g έχουν επίσης διαχωριστές ακμής μεγέθους O((gΔn)1/2).
Γραφήματα φραγμένου γένους αποτελούν ένα παράδειγμα μιας οικογένειας γραφημάτων κλειστών κάτω από την πράξη της λήψης των μικρότερων, και τα θεωρήματα διαχωρισμού ισχύουν επίσης για αυθαίρετα μικρά κλειστά οικογενειακά γραφήματα. Ειδικότερα, αν ένα οικογενειακό γράφημα έχει ένα απαγορευμένο έλασσον με h κορυφές, τότε έχει ένα διαχωριστή με O(h√n) κορυφές, και ένας τέτοιος διαχωριστής μπορεί να βρεθεί σε χρόνο  O(n1 + ε) για κάθε ε > 0.
Η μέθοδος κυκλικού διαχωρισμού των ) γενικεύεται στα γραφήματα οποιουδήποτε συστήματος d-διαστάσεων με την ιδιότητα ότι κάθε σημείο στο χώρο που καλύπτεται από το πολύ κάποιο σταθερό αριθμό  k από μπάλες, σε k-πλησιέστερα γειτονικά γραφήματαs σε d διαστάσεις, και τα γραφήματα που προκύπτουν από  πλέγματα πεπερασμένων στοιχείων. Οι σφαιρικοί διαχωριστές κατασκευάστηκαν  με αυτόν τον τρόπο χωρίζοντας  το γράφημα εισόδου σε υπογραφήματα από το πολύ n(d + 1)/(d + 2) κορυφές. Το μέγεθος των διαχωριστών για  k-ply μπάλες kγραφημάτων και γραφήματα k-πλησιέστερου γείτονα είναι O(k1/dn1 − 1/d).
Αλγόριθμοι διαίρει και βασίλευε
Η διαχωριστική αποσύνθεση μπορεί να είναι χρήσιμη στο σχεδιασμό αποτελεσματικών διαίρει και βασίλευε αλγορίθμων για την επίλυση προβλημάτων σχετικά με επίπεδα γραφήματα. Για παράδειγμα, ένα πρόβλημα που μπορεί να λυθεί με αυτόν τον τρόπο είναι να βρεθεί ο συντομότερος κύκλος σε ένα σταθμισμένο επίπεδο διαγράμματος. Αυτό μπορεί να λυθεί με τα ακόλουθα στάδια: Ο χρόνος για τις δύο αναδρομικές κλήσεις σε A και Bσε αυτόν τον αλγόριθμο υπερισχύει από το χρόνο για να εκτελέσει το Ο  (√n) να καλέσει τον αλγόριθμο του Dijkstra, έτσι ώστε ο αλγόριθμος να βρει το συντομότερο κύκλο σε Ο (n3/2 log n) χρόνο.
Ο ταχύτερος αλγόριθμος για το ίδιο πρόβλημα εύρεσης του συντομότερου κύκλου, που τρέχει σε χρόνο O(n log3n), δόθηκε από τον. ). Ο αλγόριθμος του χρησιμοποιεί την ίδια διαίρει και βασίλευε διαχωριστική δομή, αλλά χρησιμοποιεί απλό διαχωριστικό κύκλο αντί των τυχαίων διαχωριστικών, έτσι ώστε οι κορυφές τουS να ανήκουν σε μια και μόνο όψη των γραφημάτων μέσα και έξω από το διαχωριστικό του κύκλου. Στη συνέχεια, όταν αντικαθιστά το O(√n) διαχωριστή καλεί τον αλγόριθμο του Dijkstra με πιο πολύπλοκους αλγόριθμους για να βρει τις συντομότερες διαδρομές από όλες τις κορυφές σε μια μόνο όψη ενός επίπεδου γραφήματος και να συνδυάσει τις αποστάσεις από τα δύο υπογραφήματα. Για σταθμισμένα αλλά χωρίς διεύθυνση επίπεδα γραφήματα, ο συντομότερος κύκλος είναι ισοδύναμος με την ελάχιστη μείωση του δυϊκού και μπορεί να βρεθεί σε Ο (n log log n) χρόνο, και ο μικρότερος κύκλος σε ένα μη σταθμισμένο και χωρίς διεύθυνση επίπεδο γράφημα (περίμετρος του) μπορεί να βρεθεί σε χρόνο O(n). (Ωστόσο, ο ταχύτερος αλγόριθμος για μη σταθμισμένα γραφήματα δεν βασίζεται στο θεώρημα διαχωρισμού.)
Το σκίτσο του αλγορίθμου για να λύσει το πρόβλημα του είναι ως εξής.
1.Φάση προεπεξεργασίας: Κατανέμουμε το γράφημα σε προσεκτικές επιλεγμένες υποομάδες κορυφών και καθορίζουμε τις συντομότερες διαδρομές μεταξύ όλων των ζευγών των κορυφών σε αυτές τις υποομάδες, όπου οι ενδιάμεσες κορυφές σε αυτή τη διαδρομή δεν είναι το υποσύνολο. Η φάση αυτή απαιτεί ένα επίπεδο γράφημαG0 να μετατραπεί σε G χωρίς κορυφή έχοντας βαθμό μεγαλύτερο του 3.Από απόρροια του τύπου του Euler ο αριθμός των κορυφών του γραφήματος που προκύπτει θα είναι n ≤ 6n0 -12, όπου n0  είναι ο αριθμός των κορυφών του  G0. Αυτή η φάση εξασφαλίζει επίσης τις ακόλουθες ιδιότητες μιας κατάλληλης r-διαίρεσης.Μια κατάλληλη  r-διαίρεση ενός επίπεδου γραφήματος είναι μια  r-διαίρεση, έτσι ώστε,
Henzinger et. al. επέκτεινε την τεχνικήr-διαίρεσης Frederickson για την πηγή συντομότερου αλγόριθμου απλής διαδρομής σε επίπεδες γραφικές παραστάσεις για μη αρνητική άκρη μήκη και πρότεινε ένα γραμμικό αλγόριθμο. Η μέθοδός τους γενικεύει την έννοια του γραφήματος Frederickson σε κλάδους, έτσι ώστε τώρα μια  (r,s)-- διαίρεση ενός γραφήματος n κόμβων είναι μια διαίρεση σε Ο nτων περιφερειών, που το καθένα περιέχει r{O(1)}  )} κόμβους, που ο καθένας έχει το πολύ s όριο κόμβων. Εάν μια  (r, s)-διαίρεση διαιρείται επανειλημμένα σε μικρότερες περιοχές, καλείται να πάρει μια αναδρομική διαίρεση. Αυτός ο αλγόριθμος χρησιμοποιεί περίπου log*n επίπεδα των διαιρέσεων. Η αναδρομική διαίρεση αντιπροσωπεύεται από ένα  δέντρο με ρίζα τα φύλλα του οποίου επισημαίνονται με ξεχωριστή ακμή του  G. Η ρίζα του δέντρου αντιπροσωπεύει την περιοχή που αποτελείται από πλήρης-G, τα παιδιά της ρίζας αντιπροσωπεύουν τις υποπεριοχές εντός του οποίου αυτή η περιοχή διαιρείται και ούτω καθεξής. Κάθε  φύλλο (ατομική περιοχή) αντιπροσωπεύει μια περιοχή που περιέχει ακριβώς μία ακμή. Ένθετη ανατομή είναι ένας διαχωριστής που βασίζεται στη διαίρει και βασιλεύει παραλλαγή της απαλοιφής Gauss για την επίλυση αραιών συμμετρικών συστημάτων γραμμικών εξισώσεωνμε επίπεδη δομή γραφήματος, όπως αυτά προκύπτουν από την μέθοδο των πεπερασμένων στοιχείων. Περιλαμβάνει την εύρεση ενός διαχωριστή για τη γραφική παράσταση που περιγράφει το σύστημα εξισώσεων, αναδρομικά εξαλείφοντας τις μεταβλητές στα δύο υποπροβλήματα διαχωρίζονται από το άλλο με τον διαχωριστή, και στη συνέχεια εξάλειψη των μεταβλητών του διαχωριστή. Το υλικό συμπλήρωσης αυτής της μεθόδου (ο αριθμός των μη μηδενικών συντελεστών που προκύπτει από την διάσπαση Cholesky του πίνακα) είναι Ο (n log n), που επιτρέπει τη μέθοδο αυτή να είναι ανταγωνιστική με επαναληπτικές μεθόδους για τα ίδια προβλήματα.
Οι Klein, Mozes και Weimann έδωσαν έναν Ο (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.
Η επισκόπηση της προσέγγισης τους δίνεται παρακάτω.
Ένα σημαντικό μέρος αυτού του αλγορίθμου είναι η χρήση των συναρτήσεων και σε μειωμένη τιμή μήκη. Για ένα κατευθυνόμενο γράφημα G με τόξο μήκη ι(·),μια συνάρτηση των τιμών είναι μια συνάρτηση φ από τους κόμβους του G στους πραγματικούς αριθμούς. Για μια uv,τόξου, το μειωμένο μήκος σε σχέση με φ είναι ιφ(uv) = ι(uv) + φ(u) − φ(v). Μια εφικτή τιμή της συνάρτησης είναι συνάρτηση των τιμών που προκαλεί μη αρνητική μείωση σε όλα τα μήκη των τόξων τουG. Είναι χρήσιμο για τη μετατροπή ενός προβλήματος συντομότερης διαδρομής που περιλαμβάνει θετικά και αρνητικά μήκη σε ένα εκ των οποίων περιλαμβάνει μόνο μη αρνητικά μήκη, τα οποία μπορούν στη συνέχεια να λυθούν χρησιμοποιώντας τον αλγόριθμο του Dijkstra.
Ακριβής λύση των NP-hard προβλημάτων βελτιστοποίησης
Με τη χρήση δυναμικού προγραμματισμού σε αποσύνθεση δέντρου ή αποσύνθεση τμήματος ενός επίπεδου γραφήματος, πολλά NP-hard προβλήματα βελτιστοποίησης μπορεί να επιλυθούν σε χρόνο που αυξάνεται εκθετικά με √n ή √n log n. Για παράδειγμα, τα όρια αυτής της μορφής είναι γνωστά για την εύρεση μέγιστων ανεξάρτητων συνόλων, Steiner δέντρα, και Hamiltonian κύκλους, και για την επίλυση του  προβλήματος του περιπλανώμενου πωλητή για επίπεδες γραφικές παραστάσεις. Παρόμοιες μέθοδοι που περιλαμβάνουν θεωρήματα διαχωρισμού για τις γεωμετρικές γραφικές παραστάσεις μπορούν να χρησιμοποιηθούν για την Ευκλείδεια επίλυση προβλημάτων του περιπλανώμενου πωλητή και Steiner δέντρα προβλήματα κατασκευής του δέντρου στα όρια του χρόνου της ίδιας μορφής.
Για παραμετροποιημένα προβλήματα που παραδέχονται ένα πυρήνα που διατηρεί επιπεδότητα και μειώνει το γράφημα εισόδου σε ένα πυρήνα του μεγέθους γραμμικού στην παράμετρο εισόδου, αυτή η προσέγγιση μπορεί να χρησιμοποιηθεί για το σχεδιασμό  σταθερών παραμέτρων προσιτών αλγορίθμων το χρόνο λειτουργίας των οποίων εξαρτάται πολυωνυμικά από το μέγεθος του γραφήματος εισόδου και εκθετικά για √k, όπου k είναι η παράμετρος του αλγορίθμου. Για παράδειγμα, τα χρονο-όρια αυτής της μορφής είναι γνωστά για την εύρεση  κορυφαίων καλυμμάτων και κυριαρχούν σύνολα μεγέθους k.
Αλγόριθμοι προσέγγισης
Οι ) παρατήρησαν ότι το θεώρημα διαχωρισμού μπορεί να χρησιμοποιηθεί για την απόκτηση πολυωνυμικών συστημάτων προσέγγισης χρόνου για NP-hard προβλήματα βελτιστοποίησης σε επίπεδες γραφικές παραστάσεις, όπως η εύρεση του  μέγιστου ανεξάρτητου συνόλου. Συγκεκριμένα, με την περικοπή μιας ιεραρχίας διαχωριστικών στο κατάλληλο επίπεδο, μπορεί κανείς να βρει ένα διαχωριστικό του μεγέθους Ο (n/√log n) η αφαίρεση του οποίου διαχωρίζει το γράφημα σε υπογραφήματα μεγέθουςc log n, για κάθε σταθερά  c. Με το θεώρημα τεσσάρων χρωμάτων, υπάρχει και ένα ανεξάρτητο σύνολο μεγέθους τουλάχιστονn/4, έτσι ώστε οι κόμβοι απομακρύνονται διαμορφώνουν ένα αμελητέο κλάσμα του μέγιστου ανεξάρτητου συνόλου, και τα μέγιστα ανεξάρτητα σύνολα στα υπόλοιπα υπογραφήματα μπορεί να βρεθούν ανεξάρτητα του εκθετικού χρόνου στο μέγεθος τους. Με το συνδυασμό αυτής της προσέγγισης με τις μεταγενέστερες μεθόδους γραμμικού χρόνου για την κατασκευή ιεραρχικού διαχωριστή και με τον πίνακα αναζήτησης για να μοιραστεί τον υπολογισμό των ανεξάρτητων συνόλων μεταξύ ισομορφικά μπορεί να γίνει για την κατασκευή ανεξάρτητων συνόλων κορυφών μεγέθους εντός ενός παράγοντα 1 − O(1/√log n) του βέλτιστου, σε γραμμικό χρόνο. Ωστόσο, για λόγους προσέγγισης ακόμα πιο κοντά στο 1 από αυτόν τον παράγοντα, μια νεότερη προσέγγιση του (με βάση δέντρο αποσύνθεση, αλλά όχι σε επίπεδο διαχωριστές) παρέχει καλύτερη ανταλλαγές του χρόνου σε σχέση με την ποιότητα προσέγγιση.
Παρόμοια συστήματα προσέγγισης διαχωριστή που βασίζονται έχουν επίσης χρησιμοποιηθεί για την προσέγγιση άλλων σκληρών προβλημάτων, όπως το κάλυμμα κορυφής. χρησιμοποιούν διαχωριστικά με έναν διαφορετικό τρόπο για να προσεγγίσουν το πρόβλημα του περιοδεύοντος πωλητή για τη συντομότερη διαδρομή για μετρικά σταθμισμένα επίπεδα γραφήματα; Οι αλγόριθμοι τους χρησιμοποιούν δυναμικό προγραμματισμό για να βρουν τη συντομότερη διαδρομή που, σε κάθε επίπεδο της ιεραρχίας διαχωριστή, διασχίζει το διαχωριστικό ενός οριοθετημένου πολλές φορές, και δείχνουν ότι ως διάβαση δεσμεύεται αυξάνει τις εκδρομές κατασκευάστηκε με αυτόν τον τρόπο έχουν μήκη που προσεγγίζουν τη βέλτιστη περιήγηση.
Συμπιεσμένο Γράφημα
Οι διαχωριστές έχουν χρησιμοποιηθεί ως μέρος των αλγορίθμων συμπίεσης δεδομένων για την αναπαράσταση επίπεδων γραφικών παραστάσεων και άλλα διαχωριστικά γραφήματα χρησιμοποιώντας ένα μικρό αριθμό από bits. Η βασική αρχή αυτών των αλγορίθμων είναι να επιλέξουν έναν αριθμόk και επανειλημμένα να υποδιαιρεθεί το συγκεκριμένο επίπεδο γράφημα με διαχωριστικό σε O(n/k) υπογραφήματα μεγέθους το πολύ k, με O(n/√k) κορυφές στα χωρίσματα. Με την κατάλληλη επιλογή τηςk (στη πιο ανάλογη προς το λογάριθμο της n) ο αριθμός των  μη-ισομορφικών υπογραφημάτων k-κορυφών επίπεδων είναι σημαντικά μικρότερος από τον αριθμό των υπογραφημάτων στην αποσύνθεση, έτσι ώστε το γράφημα μπορεί να συμπιεστεί με την κατασκευή ενός πίνακα όλες τα πιθανά μη ισομορφικά υπογραφήματα και εκπροσωπούν κάθε υπογράφο στην αποσύνθεση διαχωριστή με το δείκτη του στον πίνακα. Το υπόλοιπο του γραφήματος, που σχηματίζεται από τις κορυφές διαχωριστή, μπορεί να αντιπροσωπεύεται ρητά ή χρησιμοποιώντας μια αναδρομική εκδοχή της ίδιας δομής δεδομένων. Χρησιμοποιώντας αυτή τη μέθοδο, επίπεδες γραφικές παραστάσεις και πολλά άλλα περιορισμένων οικογενειών επίπεδων γραφημάτων μπορούν να κωδικοποιούνται χρησιμοποιώντας έναν αριθμό bits που είναι πληροφορίες-θεωρητικά βέλτιστες: αν υπάρχουνPn n-κορυφή γραφήματα στην οικογένεια των γραφημάτων να εκπροσωπούνται, τότε ένα άτομο γράφημα στην οικογένεια μπορεί να αναπαρασταθεί χρησιμοποιώντας μόνο(1 + o(n))log2Pn bits. είναι επίσης δυνατόν να κατασκευασθούν αναπαραστάσεις αυτού του τύπου στην οποία μπορεί κανείς να δοκιμάσει γειτνίασή μεταξύ των κορυφών, τον καθορισμό του βαθμού μιας κορυφής, και οι λίστες γείτονες των κορυφών σε σταθερό χρόνο ανά ερώτημα, αυξάνοντας το πίνακα υπογράφων με πρόσθετες πληροφορίες σε μορφή πίνακα αντιπροσωπεύουν τις απαντήσεις στα ερωτήματα.
Καθολικά γραφήματα
Ένα καθολικό γράφημα για μια οικογένεια F των γραφημάτων είναι ένα γράφημα που περιέχει κάθε μέλος  Fως υπογραφήματα. Ο διαχωριστής μπορεί να χρησιμοποιηθεί για να δείξει ότι οι n-κορυφή επίπεδων γραφιμάτων έχουν καθολικά γραφήματα με n κορυφές και Ο (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-επίπεδο κορυφή γράφημα ως υπογράφημα. Μια παρόμοια κατασκευή δείχνει ότι οριοθετούνται βαθμοί επίπεδων γραφημάτων που έχουν καθολικά γραφήματα με Ο (n log n) ακμές, όπου η σταθερά κρυμμένη στο συμβολισμό Ο notation Ο εξαρτάται από το βαθμό που δεσμεύεται. Κάθε καθολικό γράφημα για επίπεδα γραφήματα (ή ακόμα και για τα δέντρα του απεριόριστου βαθμού) πρέπει να έχει Ω(n log n)ακμές, αλλά παραμένει άγνωστο αν αυτό το κατώτερο όριο ή το Ο (n3/2) άνω φράγμα είναι σφιχτό για καθολικά γραφήματα για αυθαίρετα επίπεδα γραφήματα.
Αναφορές
Κατηγορία:Θεωρία γράφων
Ρίτσαρντ Τσάμπερλεϊν
Ο Ρίτσαρντ Τσάμπερλεϊν (George Richard Chamberlain, 31 Μαρτίου 1934) είναι Αμερικανός ηθοποιός του κινηματογράφου, του θεάτρου και της τηλεόρασης και τραγουδιστής. Έγινε το ίνδαλμα της αμερικανικής νεολαίας όταν πρωταγωνίστησε στην τηλεοπτικό σειρά Dr. Kildare (1961-1966), η οποία του χάρισε έναν Χρυσό Σκούφο και το έπαθλο του πιο δημοφιλούς άνδρα ηθοποιού για τις χρονιές 1962, 1963 και 1964.