Проверка графа на планарность

Задача проверки планарности — это алгоритмическая задача проверки, является ли данный граф планарным (то есть, может ли он быть нарисован на плоскости без пересечения рёбер). Задача хорошо изучена в информатике и для неё было придумано много практических алгоритмов, многие из которых используют современные структуры данных. Большинство этих методов работают за время O(n) (линейное время), где n — число рёбер (или вершин) графа, что является асимптотически оптимальным алгоритмом [en] . Вместо простого булевского значения, выход алгоритмов проверки планарности может дать вложение графа, если граф планарен, или преграду планарности, такую как подграф Куратовского, если граф не планарен.

Содержание

Критерии планарности [ править | править код ]

Алгоритмы проверки планарности обычно пользуются теоремами теории графов, которые описывают множество планарных графов в терминах, не зависящих от рисования графов. Сюда входят

• Теорема Понтрягина — Куратовского, что граф планарен тогда и только тогда, когда он не содержит подграфа, который является подразделениемK₅ (полный граф с пятью вершинами) или K_3,3 (коммунальный граф, полный двудольный граф с шестью вершинами, три из которых соединены с каждой вершиной из другой тройки).
• Теорема Вагнера, что граф планарен тогда и только тогда, когда он не содержит минора (подграфа стягиваний), который изоморфенK₅ или K_3,3.
• Критерий планарности де Фрейсекса — Розенштиля, описывающий планарные графы в терминах упорядочения слева направо в дереве поиска в глубину.

Критерий планарности Де Фрейсекса — Розенштиля можно использовать прямо как часть алгоритма проверки планарности, в то время как теоремы Куратовского и Вагнера применяются косвенно — если алгоритм может найти копию K₅ или K_3,3 в данном графе, можно быть уверенным, что входной граф не планарен.

Другие критерии планарности, которые описывают планарные графы математически, но которые меньше пригодны для алгоритмов проверки планарности, включают критерий планарности Уитни, что граф планарен тогда и только тогда, когда его графовый матроид является также кографовым, критерий планарности Маклейна, описывающий планарные графы базисами их циклических пространств [en] , Теорема Шнайдера, описывающая планарные графы порядковой размерностью [en] ассоциированных частично упорядоченных множеств, и критерий планарности Колен де Вердьера, использующий спектральную теорию графов.

Алгоритмы [ править | править код ]

Метод добавления пути [ править | править код ]

Первым опубликованным (в 1974 году) алгоритмом проверки планарности был классический метод добавления пути Хопкрофта и Тарьяна [1] , который работал за линейное время. Имплементация алгоритма Хопкрофта и Тарьян включён в библиотеку эффективных типов данных и алгоритмов [en] Мельхорна [en] , Муцеля [en] и Неэра [2] [3] [4] . В 2012, Тейлор [5] расширил этот алгоритм для генерации всех перестановок циклических порядков рёбер для вложения двусвязных компонент.

Метод добавления вершин [ править | править код ]

Метод добавления вершин путём создания структуры данных, представляющих возможные вложения порождённого подграфа данного графа и добавления вершин по одной к этой структуре данных. Эти методы начинались с неэффективного O(n 2 ) метода, предложенный Лемпелем [en] , Ивеном [en] и Цедербаумом в 1967 [6] . Метод улучшили Ивен и Тарьян, которые нашли решение линейного времени для шага s,t-нумерации [7] , а затем улучшили Бут и Люкер, разработавшие структуру данных PQ-дерева. С этими улучшениями метод стал линейным по времени и, на практике, стал работать быстрее метода добавления путей [8] . Этот метод был также расширен, чтобы эффективно вычислять планарное вложение (рисование) для планарных графов [9] . В 1999 году Ши и Сю упростили эти методы, используя PC-дерево (некорневой вариант PQ-дерева) и обход с отложенной выборкой дерева вершин с поиском в глубину [10] .

Метод добавления рёбер [ править | править код ]

В 2004 году Бойер и Мирволд [11] разработали упрощённый алгоритм со временем работы O(n), который был навеян методом PQ-дерева, но в котором избавились от PQ-дерева и алгоритм использует добавление рёбер для вычисления планарного вложения, если такое возможно. В противном случае вычисляется подразделение Куратовского (либо графа K₅, либо графа K_3,3). Метод является одним из двух существующих в настоящее время алгоритмов (второй — алгоритм проверки планарности де Фрейсекса, де Мендеса и Розенштиля [12] [13] ). См. статью Бойера, Кортезе, Патригнами и Баттиста [14] с экспериментальным сравнением с предварительной версией алгоритма проверки планарности Бойера и Мирволда. При этом алгоритм проверки Бойера и Мирволда был расширен для выделения нескольких подразделений Куратовского непланарного входного графа со временем работы, линейно зависящим от размера выхода [15] . Исходники проверки планарности [16] [17] и выделения нескольких подразделений Куратовского [16] находятся в открытом доступе (на языке C++). Алгоритм, определяющий подграф Куратовского за линейное от количества вершин время, разработал Вильямсон в 1980-х годах [18] .

Метод последовательного построения [ править | править код ]

Другой метод использует построение по индукции 3-связных графов для последовательного построения планарного вложения любой 3-связной компоненты графа G (а потому и планарного вложения самого графа G) [19] . Построение начинается с K₄ и определяется таким образом, что любой промежуточный граф на пути к полной компоненте является снова 3-связным. Поскольку такие графы имеют единственное вложение (с точностью до выбора внешней грани), следующий больший граф, если он остаётся планарным, должен быть уточнением предыдущего графа. Это позволяет свести проверку планарности к просто проверке, будет ли следующее добавленное ребро иметь оба конца на внешней грани текущего вложения. Будучи концептуально очень простым (и он даёт линейное время работы), метод обладает большой сложностью поиска последовательности построения.

Похожие темы научных работ по математике , автор научной работы — Гладков Л. А.

Текст научной работы на тему «Алгоритм определения планарности графа»

Материалы Всероссийской конференции “Интеллектуальные САПР-96”

поле, и по одной подзадаче для размещения элементов внутри каждого блока. Эффективность данного метода распределения является высокой, поскольку все подзадачи (кроме размещающей блоки, которую необходимо решить предварительно) являются независимыми, следовательно, отсутствует необходимость во взаимном обмене данными и синхронизации выполнения. Основным критерием, предъявляемым к алгоритму распределения, с точки зрения скорости решения всей задачи, в целом, является обеспечение максимально близких друг к другу времен решения всех подзадач.

При использовании итерационного подхода объектом распределения являются отдельные итерации. Задачей алгоритма распределения является генерация исходных параметров некоторого итерационного шага на основании результатов предыдущих шагов, распределяемые же фрагменты задачи выполняют оценку и улучшение исходных параметров соответствующей итерации. Следует отметить, что здесь, в отличие от блочно — иерархического подхода, процесс распределения идет непрерывно в течение всего времени решения задачи. Важной является проблема объединения результатов, полученных при параллельном выполнении некоторых итераций. С этой точки зрения представляется перспективным использование распределенной обработки применительно к генетическим и эволюционным методам.

Безусловно, оба эти подхода могут использоваться совместно, так, подзадачи, полученные на основе блочно иерархического метода, в свою очередь оказываются распределенными по отдельным итерациям. Аналогично каждая итерация может быть выполнена с использованием блочно иерархического распределения. В целом распределенное решение задачи размещения представляется высокоэффективным как с точки зрения времени выполнения, так и с точки зрения оптимальности использования вычислительных ресурсов.

Для задачи трассировки основным методом распределения также является блочно иерархический, однако общая эффективность распределенной трассировки представляется не столь высокой, как для задачи размещения. Это в первую очередь связано с тем, что необходимо учитывать взаимовлияние блоков на их границах, приводящее к высоким объемам информации, передаваемым по сети от одной подзадачи к другой. Улучшить эффективность распределенной трассировки можно посредством использования алгоритмов, ориентированных на макродискреты, либо методов анализа структуры исходной задачи, таких, как выделение изоморфных компонент.

Таким образом, использование распределенных методов позволит существенно ускорить решение задач конструкторского проектирования ЭВА посредством минимальных затрат.

Л. А. Гладков Алгоритм определения планарности графа

Задача определения планарности графа относится к числу важнейших задач САПР и состоит в нахождении такого представления графа, при котором ребра рассматриваемого графа не пересекаются между собой. Идея описываемого алгоритма определения планарности графов базируется на известном принципе Харари [1]. Согласно этому принципу, граф в планарен в том случае, когда можно выделить к — циклов, таких, что любое ребро графа принадлежит одновременно двум и только двум циклам из выделенного множества. Тогда алгоритм определения планарности графа в заключается в выделении из матрицы всех возможных циклов графа(Вгш) субматрицы(Вг1) такой, что количество строк

подматрицы Вг1 равно ш — п + 2, где ш — число ребер ,а п — число вершин графа С; и каждое ребро графа в принадлежит одновременно двум и только двум строкам субматрицы Вг1 [2,3].

Сложность задачи состоит помимо прочего в том, что прежде чем перейти собственно к определению планарности необходимо сформировать матрицу всех Циклов, что подразумевает собой полный перебор всех возможных путей в графе. В силу этого при увеличении размерности графа (п > 40) наблюдается резкий рост ВСА.

В настоящей статье предложен ряд эвристик, позволяющих если не исключить, то по крайней мере значительно уменьшить вероятность полного перебора.

Остановимся более подробно на предлагаемом алгоритме.

Прежде, чем приступить к формированию матрицы циклов, мы производим нумерацию всех ребер графа. После чего формируется список смежности, где число столбцов соответствует числу вершин графа, число строк — локальным степеням вершин графа, а элементы матрицы представляют собой номера вершин графа, инцидентных вершине с номером, соответствующим номеру текущего столбца. В такой матрице выбирается столбец с максимальным количеством строк(при наличии столбцов с равным количеством строк — любой из них) и с этого столбца начинается процесс генерации циклов к той длины. В рабочем столбце выбирается первая вершина, после чего мы переходим к столбцу с номером, соответствующим номеру текущей вершины. При этом не рассматриваются уже задействованные на предыдущих шагах вершины, а также, до достижения к • того шага, начальная вершина хО. При достижении к • той вершины алгоритм проверяет возможность замыкания цикла, т.е. наличие связи между вершинами хк и хО. В случае, если на любом из шагов обнаруживается невозможность дальнейшего наращивания(замыкания), алгоритм возвращается на один шаг назад и просматривает другие возможности для выбора пути. Таким образом, формируется некоторое множество циклов, представляющих собой цепочки вида хО — х1 — х2 хк — хО. После того, как просмотрены все возможности и сформированы все циклы, использующие вершину хО в качестве начальной, из исходного списка удаляется текущий столбец, а также из всех столбцов списка удаляются вершины, соответствующие номеру текущего столбца, после чего процесс потеряется. Причем, для того чтобы избежать повторной генерации одинаковых циклов, Достаточно в процессе работы алгоритма отслеживать вторую и к-тую позиции формируемых цепочек. Для этих целей необходимо, чтобы вершины участвующие в уже сформированных циклах, на к-той позиции, не были задействованы при дальнейшей генерации на второй позиции. Вершины, использовавшиеся в процессе генерации на к той позиции и не приведшие к замыканию цикла, могут заноситься в отдельный список и в дальнейшем исключаться из рассмотрения в качестве варианта для заполнения к — той позиции, что позволяет сократить число просматриваемых вариантов.

После того, как в результате работы алгоритма сформированы все возможные Циклы длины к, они заносятся в матрицу Вгш. Далее происходит проверка полученной информации. Данный процесс для краткости можно записать в виде следующего словесного алгоритма:

1. Подсчет числа строк г и числа единиц х в каждом столбце матрицы Вт.

2. В случае, если выполняется условие: г^т-п + 2их^2, то переход к п.З, если нет, то запускается процесс генерации циклов длины к + 1.

3. В матрице Впв выделяются столбцы, содержащие точно две единицы.

4. Сформированный таким образом базис циклов Вм проверяется на наличие столбцов с числом единиц х > 2. Если условие выполняется, то запускается процесс генерации циклов длины к + 1, если нет, то переход к п.5.

5. Рассматриваемый базис Вм проверяется на предмет выполнения условия г = т — п + 2. Если условие выполняется, то переход к п.7, если нет, то переход к п.б.

6. Происходит последовательный перебор циклов, записанных в матрице Вт, но не вошедших в формируемый базис Вм на предмет дополнения базиса ВГ| до г, при соблюдении условия х = 2. В случае выполнения данной задачи — переход к п.7, в противном случае запускается процесс генерации циклов длины к + 1.

7. Исходный граф планарен, работа алгоритма завершена.

Проиллюстрируем работу описанного алгоритма на примере.

Пусть задана ма1рица смежности произвольного графа Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Определение. Любой граф, гомеоморфный плоскому, называется планарным. Говорят, что граф допускает плоскую укладку, если его можно изобразить как плоский. Например, граф, показанный на рис.1, плоский.

Рис. 1

Существуют также и непланарные графы. На рис.2 показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K₅ и K_3,3 соответственно.

Рис. 2

Теорема. Граф является планарным, если не содержит в себе подграфов, гомеоморфных K₅ или K_3,3.

Если ли у кого примеры реализации данной проверки?