4551
правка
Проверка на планарность: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Планарное вложение == Постановка задачи == Задача заключае…») |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Первый алгоритм с линейным временем исполнения предложили Хопкрофт и Тарьян [5], проанализировав итеративную версию рекурсивного алгоритма, разработанного Ауслендером и Партером [1] и модифицированного Голдштейном [ ]. Алгоритм основывается на следующем наблюдении: связный граф является планарным в том и только том случае, если все его двусвязные компоненты являются планарными. Рекурсивный алгоритм последовательно обрабатывает каждую двусвязную компоненту: найти разделяющий цикл (separating cycle) C и разбиение ребер G, не принадлежащих C; определить компоненту разбиения как состоящую из ребер, связанных путем в G, и не включающую ребер из C; рекурсивно рассмотреть каждую циклическую компоненту разбиения. Если каждая компонента разбиения является планарной, а все компоненты могут быть объединены с C в планарный граф, то граф G является планарным. | Первый алгоритм с линейным временем исполнения предложили Хопкрофт и Тарьян [5], проанализировав итеративную версию рекурсивного алгоритма, разработанного Ауслендером и Партером [1] и модифицированного Голдштейном [4]. Алгоритм основывается на следующем наблюдении: связный граф является планарным в том и только том случае, если все его двусвязные компоненты являются планарными. Рекурсивный алгоритм последовательно обрабатывает каждую двусвязную компоненту: найти разделяющий цикл (separating cycle) C и разбиение ребер G, не принадлежащих C; определить компоненту разбиения как состоящую из ребер, связанных путем в G, и не включающую ребер из C; рекурсивно рассмотреть каждую циклическую компоненту разбиения. Если каждая компонента разбиения является планарной, а все компоненты могут быть объединены с C в планарный граф, то граф G является планарным. | ||
Другой метод определения планарности предложили Лемпел, Ивен и Седербаум [ ]. Алгоритм начинает работу с вложения единичной вершины и ребер, смежных с этой вершиной; затем он рассматривает вершину, смежную с одним из этих ребер. Для корректности работы алгоритма вершины следует рассматривать в определенном порядке. Алгоритм был впервые реализован за время O(n) Бутом и Люкером [2], использовавшими эффективную реализацию структуры данных PQ-деревьев. Более простые реализации этого алгоритма предложили Бойер и Мирволд [ ], а также Ши и Хсу [8]. | Другой метод определения планарности предложили Лемпел, Ивен и Седербаум [6]. Алгоритм начинает работу с вложения единичной вершины и ребер, смежных с этой вершиной; затем он рассматривает вершину, смежную с одним из этих ребер. Для корректности работы алгоритма вершины следует рассматривать в определенном порядке. Алгоритм был впервые реализован за время O(n) Бутом и Люкером [2], использовавшими эффективную реализацию структуры данных PQ-деревьев. Более простые реализации этого алгоритма предложили Бойер и Мирволд [3], а также Ши и Хсу [8]. | ||
Тутте предложил алгебраический метод прямолинейного вложения графа, который в случае, когда граф является трехсвязным и планарным, гарантирует построение планарного вложения. Основная идея заключается в следующем: вершины одной грани графа фиксируются, становясь углами выпуклого многогранника, а затем производится вложение всех остальных вершин как геометрического среднего их соседей. | Тутте предложил алгебраический метод прямолинейного вложения графа, который в случае, когда граф является трехсвязным и планарным, гарантирует построение планарного вложения. Основная идея заключается в следующем: вершины одной грани графа фиксируются, становясь углами выпуклого многогранника, а затем производится вложение всех остальных вершин как геометрического среднего их соседей. | ||
== Применение == | == Применение == | ||