| dbo:abstract
|
- Στη θεωρία γραφημάτων, το θεώρημα διαχωριστικού επιπέδου είναι μια μορφή για επίπεδες γραφικές παραστάσεις, που αναφέρει ότι οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να χωριστεί σε μικρότερα κομμάτια αφαιρώντας ένα μικρό αριθμό κορυφών. Συγκεκριμένα, η απομάκρυνση της O(√n) κορυφής από ένα γράφημα με n-κορυφές (όπου το O επικαλείται επικαλείται μεγάλο Ο συμβολισμό) μπορεί να χωρίσει το γράφημα σε ασυνεχείς υπογράφους καθένα από τα οποία έχει το πολύ 2n / 3 κορυφές. Μια ηπιότερη μορφή του θεωρήματος διαχωρισμού με O(√n log n) κορυφές στο διαχωριστή αντί για O(√n) αρχικά αποδεικνύεται από τον ), καθώς και η μορφή με την στενή ασύμπτωτη δεσμεύεται από το μέγεθος της διαχωριστικής που πρωτοαποδείχτηκε από τον ). Δεδομένου του έργου τους, το θεώρημα διαχωρισμού έχει αποδειχτεί ξανά με διάφορους τρόπους,ο σταθερός στη θέση O(√n)όρος του θεωρήματος έχει βελτιωθεί, και έχει επεκταθεί σε ορισμένες κατηγορίες των μη επίπεδων γραφικών παραστάσεων. Η επαναλαμβανόμενη εφαρμογή του θεωρήματος διαχωρισμού παράγει μια ιεραρχία ξεχωριστή η οποία μπορεί να λάβει τη μορφή είτε ενός βασικού μέρους αποσύνθεσης (δέντρου) ή μιας διακλαδωσης-αποσύνθεσης του γραφήματος. Διαχωριστικές ιεραρχίες μπορεί να χρησιμοποιηθούν για να επινοήσουν αποδοτικούς αλγορίθμους του τύπου διαίρει και βασίλευε για επίπεδα γραφήματα, και δυναμικοί προγραμματισμοί αυτών των ιεραρχιών μπορούν να χρησιμοποιηθούν για να σχεδιάσουν και σταθερών παραμέτρων εύκολων αλγορίθμων για την επίλυση προβλημάτων βελτιστοποίησης σε αυτά τα γραφήματα. Οι διαχωριστικές ιεραρχίες μπορεί επίσης να χρησιμοποιηθούν σε , μια αποτελεσματική παραλλαγή της για την επίλυση αραιών συστημάτων γραμμικών εξισώσεων που προκύπτουν από μεθόδους πεπερασμένων στοιχείων. (el)
- En théorie des graphes, le théorème du séparateur planaire, stipule que tout graphe planaire peut être divisé en parties plus petites en supprimant un petit nombre de sommets. Plus précisément, le théorème affirme qu'il existe un ensemble de sommets d'un graphe à sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus sommets. (fr)
- In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most vertices. A weaker form of the separator theorem with vertices in the separator instead of was originally proven by , and the form with the tight asymptotic bound on the separator size was first proven by . Since their work, the separator theorem has been reproven in several different ways, the constant in the term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs. Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph. Separator hierarchies may be used to devise efficient divide and conquer algorithms for planar graphs, and dynamic programming on these hierarchies can be used to devise exponential time and fixed-parameter tractable algorithms for solving NP-hard optimization problems on these graphs. Separator hierarchies may also be used in nested dissection, an efficient variant of Gaussian elimination for solving sparse systems of linear equations arising from finite element methods. Beyond planar graphs, separator theorems have been applied to other classes of graphs including graphs excluding a fixed minor, nearest neighbor graphs, and finite element meshes. The existence of a separator theorem for a class of graphs can be formalized and quantified by the concepts of treewidth and polynomial expansion. (en)
- Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами (здесь O обозначает «O» большое) можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин. Более слабую теорему о планарном разбиении с O(√n log n) вершинами в сепараторе вместо O(√n) доказал Унгар, а теорему с более сильной асимптотической границей на размер сепаратора первыми доказали Липтон и Тарьян. После их статей теорема о планарном разбиении была передоказана несколькими различными путями, константа O(√n) в утверждении теоремы была улучшена. Теорема была расширена также на некоторые классы непланарных графов. Повторное приложение теоремы о разбиении даёт иерархию сепараторов, которое может принять вид либо древесной декомпозиции, либо декомпозиции графа на ветви. Иерархию сепараторов можно использовать для разработки эффективных алгоритмов «Разделяй и властвуй» для планарных графов, а динамическое программирование на этих иерархиях можно использовать для разработки алгоритмов экспоненциального времени и алгоритмов для решения NP-трудных оптимизационных задач на этих графах. Иерархию сепараторов можно также использовать во , эффективном варианте исключений Гаусса для решения разреженных систем линейных алгебраических уравнений, возникающих в методе конечных элементов. Теория двумерности Эрика Демайна, Фёдора Фомина, Мухаммеда Хаджигайи и Димитроса Тиликоса обобщает и существенно расширяет область применения теоремы о планарном разбиении на обширное множество задач на планарных графах и, более обще, на графах, не содержащих определённого минора. (ru)
- У теорії графів, теорема про планарне розбиття є формою ізопериметричної нерівності для планарних графів, що стверджує, що будь-який планарний граф можна розділити на дрібніші шматки, видаляючи невелику кількість вершин. Зокрема, видалення вершин з -вершинного графа (де О використано по аналогії з O великим ) може розділити граф на непересічні підграфи, кожен з яких має не більше вершин. Більш слабка форма теореми розбиття з вершинами в розбитті, а не була спочатку доведена Унгаро (1951), а форма з близьким асимптотична оцінка від розміру розбиття вперше доведено по Lipton і Tarjan (1979). З їх роботі, теорема розбиття був reproven кількома різними способами, постійна в термін теореми була покращена, і це був продовжений до певних класів не планарних графів. Повторне застосування теореми розбиття виробляє роздільник ієрархії, які можуть приймати форму або або графу. Розбиття ієрархії можуть бути використані для розробки ефективного алгоритму розділяю і володарю для планарних графів, і динамічне програмування на цих ієрархій може бути використаний для розробки експоненціальне час і фіксованою параметрів згідливим алгоритми для вирішення NP-важкою задачі оптимізації на цих графіках. Розбиття ієрархії також можуть бути використані в вкладених перетинів, ефективного варіанту Гаусса для вирішення розріджених систем лінійних рівнянь, що випливають з методів кінцевих елементів. Теорія Двовимірності Демейна, Фоміна, Hajiaghayi і Thilikos узагальнює і значно розширює застосовність теореми розбиття для величезної множини задач мінімізації планарних графів і в більш загальному графі за винятком фіксованих графів-мінорів. (uk)
|
| rdfs:comment
|
- En théorie des graphes, le théorème du séparateur planaire, stipule que tout graphe planaire peut être divisé en parties plus petites en supprimant un petit nombre de sommets. Plus précisément, le théorème affirme qu'il existe un ensemble de sommets d'un graphe à sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus sommets. (fr)
- Στη θεωρία γραφημάτων, το θεώρημα διαχωριστικού επιπέδου είναι μια μορφή για επίπεδες γραφικές παραστάσεις, που αναφέρει ότι οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να χωριστεί σε μικρότερα κομμάτια αφαιρώντας ένα μικρό αριθμό κορυφών. Συγκεκριμένα, η απομάκρυνση της O(√n) κορυφής από ένα γράφημα με n-κορυφές (όπου το O επικαλείται επικαλείται μεγάλο Ο συμβολισμό) μπορεί να χωρίσει το γράφημα σε ασυνεχείς υπογράφους καθένα από τα οποία έχει το πολύ 2n / 3 κορυφές. (el)
- In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most vertices. (en)
- У теорії графів, теорема про планарне розбиття є формою ізопериметричної нерівності для планарних графів, що стверджує, що будь-який планарний граф можна розділити на дрібніші шматки, видаляючи невелику кількість вершин. Зокрема, видалення вершин з -вершинного графа (де О використано по аналогії з O великим ) може розділити граф на непересічні підграфи, кожен з яких має не більше вершин. (uk)
- Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами (здесь O обозначает «O» большое) можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин. (ru)
|
