Планарный граф

«Треугольный график» перенаправляется сюда. О линейных графах полных графов см. Линейный график § Сильно регулярные и совершенные линейные графы . Для триангулированных графов см. Хордальный граф . Графики данных, построенные по трем переменным, см. в разделе Тройной график .

Примеры графиков
Планарный	Неплоский
Граф бабочки	Полный граф К 5
Полный график К 4	График полезности К 3,3

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

Любой граф, который можно нарисовать на плоскости, можно нарисовать и на сфере , и наоборот, посредством стереографической проекции .

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

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

Плоские графы обобщаются до графов, которые можно нарисовать на поверхности заданного рода . В этой терминологии плоские графы имеют род 0, поскольку плоскость (и сфера) являются поверхностями рода 0. см. в разделе « Встраивание графов Другие связанные темы ».

Критерии планарности

Куратовского

Доказательство без слов того, что граф гиперкуба неплоский , с использованием теорем Куратовского или Вагнера и нахождением либо K ₅ (вверху), либо K _3,3 (внизу) подграфов.

Польский теорема математик Казимеж Куратовский дал характеристику плоских графов в терминах запрещенных графов , теперь известную как Куратовского :

Конечный граф планарен тогда и только тогда, когда он не содержит подграфа , являющегося подразделением полного графа К ₅ или полного двудольного графа К _3,3 ( граф полезности ).

Подразделение • графа происходит в результате вставки вершин в ребра (например, изменения ребра —— • на • — • — • ) ноль или более раз.

Пример графа без подграфа K ₅ или K _3,3 . Однако он содержит подразделение K _3,3 и поэтому неплоский.

Вместо рассмотрения подразделений теорема Вагнера касается миноров :

Конечный граф является планарным тогда и только тогда, когда он не имеет K ₅ или K _3,3 в качестве минора .

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

Анимация, показывающая, что граф Петерсена содержит минорный изоморфен графу K _3,3 и, следовательно, непланарен.

Клаус Вагнер задал более общий вопрос, определяется ли какой-либо минорно-замкнутый класс графов конечным набором « запрещенных миноров ». Теперь это теорема Робертсона-Сеймура , доказанная в длинной серии статей. На языке этой теоремы K ₅ и K _3,3 — запрещенные миноры для класса конечных плоских графов.

Другие критерии

На практике сложно использовать критерий Куратовского, чтобы быстро решить, является ли данный граф плоским. Однако существуют быстрые алгоритмы решения этой задачи: для графа с n вершинами можно за время O ( n ) (линейное время) определить, может ли граф быть планарным или нет (см. Проверка планарности ).

Для простого связного плоского графа с v вершинами, e ребрами и f выполняются следующие простые условия гранями при v ≥ 3 :

• Теорема 1. e ≤ 3 v – 6 ;
• Теорема 2. Если циклов длины 3 нет, то e ⩽ 2 v – 4 .
• Теорема 3. f ≤ 2 v – 4 .

В этом смысле планарные графы являются разреженными графами , поскольку они имеют только O ( v ) ребер, асимптотически меньшие, чем максимальное O ( v). ² ) . Граф K3,3 _. , например, имеет 6 вершин, 9 ребер и ни одного цикла длины 3. Поэтому по теореме 2 он не может быть плоским Эти теоремы обеспечивают необходимые условия планарности, которые не являются достаточными условиями, и поэтому могут использоваться только для доказательства того, что граф не планарен, а не того, что он планарен. Если обе теоремы 1 и 2 не работают, можно использовать другие методы.

• Критерий планарности Уитни дает характеристику, основанную на существовании двойственного алгебраического элемента;
• Критерий планарности Мак Лейна дает алгебраическую характеристику конечных плоских графов через их пространства циклов ;
• Критерий планарности Фрайссеха – Розенштиля дает характеристику, основанную на существовании двуразделения ребер кодерева дерева поиска в глубину. слева направо Он занимает центральное место в алгоритме проверки планарности ;
• Теорема Шнайдера дает характеристику планарности в терминах размерности частичного порядка ;
• Критерий планарности Колена де Вердьера дает характеристику, основанную на максимальной кратности второго собственного значения некоторых операторов Шредингера, определенных графиком.
• Теорема Ханани-Тутте утверждает, что граф является плоским тогда и только тогда, когда у него есть рисунок, на котором каждая независимая пара ребер пересекает четное количество раз; его можно использовать для характеристики плоских графов с помощью системы уравнений по модулю 2.

Свойства

Формула Эйлера

Основная статья: Эйлерова характеристика § Плоские графы

Формула Эйлера гласит, что если конечный связный плоский граф нарисован на плоскости без каких-либо пересечений ребер, а v — количество вершин, e — количество ребер, а f — количество граней (областей, ограниченных ребрами, включая внешняя, бесконечно большая область), то

$v-e+f=2.$

В качестве иллюстрации в графе-бабочке приведенном выше v = 5 , e = 6 и f = 3 . В общем, если это свойство справедливо для всех плоских графов f граней, любое изменение графа, которое создает дополнительную грань, сохраняя при этом планарность графа, сохранит v – e + f инвариантом. Поскольку это свойство справедливо для всех графов с f = 2 , по математической индукции оно справедливо для всех случаев. Формулу Эйлера также можно доказать следующим образом: если граф не является деревом , то удалите ребро, завершающее цикл . Это уменьшает e и f на единицу, оставляя v – e + f постоянным. Повторяйте, пока оставшийся граф не станет деревом; деревья имеют v = e + 1 и f = 1 , что дает v – e + f = 2 , т. е. эйлерова характеристика равна 2.

В конечном связном простом ; плоском графе любая грань (кроме, возможно, внешней) ограничена как минимум тремя рёбрами, и каждое ребро касается не более чем двух граней используя формулу Эйлера, можно затем показать, что эти графы разрежены в том смысле, что если v ≥ 3 :

$e\leq 3v-6.$

Диаграмма Шлегеля правильного додекаэдра , образующая плоский граф из выпуклого многогранника.

Формула Эйлера справедлива и для выпуклых многогранников . Это не случайно: каждый выпуклый многогранник можно превратить в связный простой плоский граф, используя диаграмму Шлегеля многогранника — перспективную проекцию многогранника на плоскость с центром перспективы, выбранным вблизи центра одного из грани многогранника. Не каждый плоский граф таким образом соответствует выпуклому многограннику: например, деревья этого не делают. Теорема Стейница утверждает, что многогранные графы, образованные из выпуклых многогранников, представляют собой в точности конечные 3-связные простые планарные графы. В более общем смысле формула Эйлера применима к любому многограннику, грани которого представляют собой простые многоугольники , образующие поверхность, топологически эквивалентную сфере, независимо от ее выпуклости.

Средняя степень

Связные плоские графы с более чем одним ребром подчиняются неравенству 2 e ≥ 3 f , поскольку каждая грань имеет как минимум три инцидентности ребра грани, и каждое ребро вносит ровно два инцидентности. Путем алгебраических преобразований этого неравенства с помощью формулы Эйлера v – e + f = 2 следует , что для конечных плоских графов средняя степень строго меньше 6. Графы с более высокой средней степенью не могут быть планарными.

Графики монет

Основная статья: Теорема об упаковке кругов

Пример теоремы об упаковке кругов на K ⁻ ₅ — полный граф из пяти вершин минус одно ребро.

Мы говорим, что две окружности, нарисованные на плоскости, целуются (или соприкасаются ) всякий раз, когда они пересекаются ровно в одной точке. «Граф монет» — это граф, образованный набором кругов, никакие два из которых не имеют перекрывающихся внутренних частей, путем создания вершины для каждого круга и ребра для каждой пары целующихся кругов. Теорема об упаковке кругов , впервые доказанная Полом Кебе в 1936 году, утверждает, что граф является плоским тогда и только тогда, когда он является графом монеты.

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

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

Коэффициент связности или плотность D планарного графа или сети — это отношение числа f – 1 ограниченных граней (того же, что и схемный ранг графа по критерию планарности Мак Лейна ) к его максимально возможным значениям 2 v – 5 для графа с v вершинами:

$D={\frac {f-1}{2v-5}}$

Плотность подчиняется 0 ≤ D ≤ 1 , причем D = 0 для полностью разреженный планарный граф (дерево) и D = 1 для полностью плотного (максимального) планарного графа.

Двойной график

Планарный граф и его двойственный граф

Учитывая вложение G связного графа (не обязательно простого) в плоскость без пересечений ребер, мы строим двойственный граф G* следующим образом: мы выбираем по одной вершине в каждой грани G (включая внешнюю грань) и для каждого ребра e в G мы вводим новое ребро в G*, соединяющее две вершины в G*, соответствующие двум граням в G, которые встречаются в точке e . Более того, это ребро нарисовано так, что оно пересекает e ровно один раз и что никакое другое ребро G или G* не пересекается. Тогда G* снова является вложением (не обязательно простого) плоского графа; у него столько же ребер, сколько G , столько вершин, сколько G граней, и столько граней, сколько G имеет вершин. Термин «двойственный» оправдан тем, что G ** = G ; здесь равенство есть эквивалентность вложений на сфере . Если G — планарный граф, соответствующий выпуклому многограннику, то G* — планарный граф, соответствующий двойственному многограннику.

Дуальные графы полезны, поскольку многие свойства двойственного графа простым образом связаны со свойствами исходного графа, что позволяет доказывать результаты о графах путем изучения их двойственных графов.

Хотя двойственный граф, построенный для конкретного вложения, уникален (с точностью до изоморфизма ), графы могут иметь разные (т.е. неизоморфные) двойственные графы, полученные из разных (т.е. негомеоморфных ) вложений.

Семейства плоских графов

Максимальные планарные графы

Граф Гольднера –Харири максимально планарен. Все его грани ограничены тремя ребрами.

Простой граф называется максимальным планарным, если он планарный, но добавление любого ребра (в заданном множестве вершин) разрушит это свойство. Все грани (включая внешнюю) затем ограничиваются тремя краями, что объясняет альтернативный термин « триангуляция плоскости» . Альтернативные названия «треугольный граф». или «триангулированный график» также использовались, но неоднозначны, поскольку чаще относятся к линейному графику полного графа и к хордальным графам соответственно. Любой максимальный планарный граф не менее чем 3-связен.

Если максимальный планарный граф имеет v вершин с v > 2 , то он имеет ровно 3 v – 6 ребер и 2 v – 4 грани.

Аполлоновы сети — это максимальные планарные графы, образованные путем многократного разделения треугольных граней на тройки меньших треугольников. Эквивалентно, это плоские 3-деревья .

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

Внепланарные графики

Внепланарные графы — это графы с вложением в плоскость, все вершины которого принадлежат неограниченной грани вложения. Каждый внешнепланарный граф планарен, но обратное неверно: K ₄ планарен, но не внешнепланарен. Теорема, подобная теореме Куратовского, утверждает, что конечный граф является внешнепланарным тогда и только тогда, когда он не содержит подразделений K ₄ или K _2,3 . Вышесказанное является прямым следствием того факта, что граф G является внешнепланарным, если граф, образованный из G добавлением новой вершины с ребрами, соединяющими его со всеми остальными вершинами, является плоским графом.

1-внепланарное вложение графа аналогично внешнепланарному вложению. При k > 1 плоское вложение называется k -внепланарным, если удаление вершин на внешней грани приводит к ( k – 1) -внепланарному вложению. Граф называется k -внепланарным, если он имеет k -внепланарное вложение.

Графики Халина

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

Восходящие планарные графики

Планарный граф, направленный вверх, — это направленный ациклический граф , который можно нарисовать на плоскости, ребра которого представляют собой непересекающиеся кривые, последовательно ориентированные вверх. Не каждый планарный ориентированный ациклический граф является планарным вверх, и NP-полной является проверка того, является ли данный граф планарным вверх.

Выпуклые плоские графики

Планарный граф называется выпуклым, если все его грани (включая внешнюю грань) являются выпуклыми многоугольниками . Не все плоские графы имеют выпуклое вложение (например, полный двудольный граф K _2,4 ). Достаточным условием того, что граф может быть нарисован выпуклым, является то, что он является подразделением планарного графа , связанного с 3 вершинами . Пружинная теорема Тутте даже утверждает, что для простых плоских графов, связанных с 3 вершинами, положение внутренних вершин может быть выбрано как среднее значение его соседей.

Представимые в словах плоские графы

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

Теоремы

Перечисление планарных графов

Асимптотика на числа (помеченных) плоских графов $n$ вершины $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$, где $\gamma \approx 27.22687$ и $g\approx 0.43\times 10^{-5}$.

Почти все планарные графы имеют экспоненциальное число автоморфизмов.

Количество непомеченных (неизоморфных) плоских графов на $n$ вершины находятся между $27.2^{n}$ и $30.06^{n}$.

Другие результаты

Теорема о четырёх цветах утверждает, что каждый плоский граф раскрашивается в 4 цвета (т. е. 4-дольный).

Теорема Фари утверждает, что каждый простой плоский граф допускает представление в виде плоского прямолинейного графа . Универсальный набор точек — это набор точек, такой, что каждый плоский граф с n вершинами имеет такое вложение со всеми вершинами в наборе точек; существуют универсальные множества точек квадратичного размера, образованные взятием прямоугольного подмножества целочисленной решетки . Каждый простой внешнепланарный граф допускает такое вложение в плоскость, что все вершины лежат на фиксированной окружности, а все ребра представляют собой отрезки прямых, лежащие внутри диска и не пересекающиеся, поэтому с n -вершинами правильные многоугольники универсальны для внешнепланарных графов.

Гипотеза Шейнермана (теперь теорема) утверждает, что каждый плоский граф можно представить как граф пересечений на отрезков прямой плоскости.

Теорема о плоском сепараторе утверждает, что каждый планарный граф с n -вершинами можно разделить на два подграфа размером не более 2 n /3 удалением O( √ n ) вершин. Как следствие, плоские графы также имеют ширину дерева и ширину ветвей O( √ n ).

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

Для двух плоских графов с v вершинами можно за время O( v они ) определить, изоморфны или нет (см. также проблему изоморфизма графов ).

Любой планарный граф на n узлах имеет не более 8 (n-2) максимальных клик, откуда следует, что класс плоских графов — это класс с малым числом клик.

Обобщения

Вершинный граф — это граф, который можно сделать плоским, удалив одну вершину, а k -верхний граф — это граф, который можно сделать плоским, удалив не более k вершин.

1 -планарный граф — это граф, который можно нарисовать на плоскости не более чем с одним простым пересечением на каждое ребро, а k -планарный граф — это граф, который можно нарисовать не более чем с k простыми пересечениями на каждое ребро.

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

Тороидальный граф — это граф, который можно вложить без пересечений на торе . В более общем смысле, род графа — это минимальный род двумерной поверхности, в которую граф может быть вложен; плоские графы имеют род ноль, а неплоские тороидальные графы имеют род один. Каждый граф можно без пересечений вложить в некоторую (ориентируемую, связную) замкнутую двумерную поверхность (сферу с ручками), и, таким образом, род графа корректно определен. Очевидно, что если граф можно вложить без пересечений в (ориентируемую, связную, замкнутую) поверхность рода g, то его можно вложить без пересечений во все (ориентируемые, связные, замкнутые) поверхности большего или равного рода. В теории графов есть и другие понятия, которые называются «родом X» с некоторым квалификатором «X»; в целом они отличаются от определенного выше понятия «род» без каких-либо определителей. В частности, неориентируемый род графа (с использованием неориентируемых поверхностей в его определении) для общего графа отличается от рода этого графа (с использованием ориентируемых поверхностей в его определении).

Любой граф можно вложить в трехмерное пространство без пересечений. Фактически, любой граф можно нарисовать без пересечений в схеме с двумя плоскостями, где две плоскости расположены друг над другом, а ребрам разрешено «подпрыгивать вверх» и «падать вниз» из одной плоскости в другую в любом месте. (не только в вершинах графа), чтобы ребра могли избегать пересечений с другими ребрами. Это можно интерпретировать как утверждение о том, что можно создать любую электрическую проводящую сеть с помощью двусторонней печатной платы , где может быть выполнено электрическое соединение между сторонами платы (как это возможно в случае типичных реальных печатных плат, с электрическими соединениями на верхней стороне платы обеспечивается кусками провода, а на нижней стороне - медными дорожками, встроенными в саму плату, а электрическое соединение между сторонами платы достигается путем сверления отверстий, пропускания проводов через отверстия и пайки их . в рельсы); это также можно интерпретировать как утверждение, что для построения любой дорожной сети нужны только мосты или только туннели, а не то и другое (двух уровней достаточно, 3 не нужны). Также в трехмерном пространстве тривиален вопрос о построении графа без пересечений. Однако трёхмерный аналог плоских графов даёт бессвязно встраиваемые графы — графы, которые можно встроить в трехмерное пространство таким образом, что никакие два цикла не будут топологически связаны друг с другом. По аналогии с характеристиками Куратовского и Вагнера плоских графов как графов, которые не содержат K ₅ или K _3,3 в качестве минора, бессвязно встраиваемые графы могут быть охарактеризованы как графы, которые не содержат в качестве минора ни одного из семь графов в семье Петерсенов . По аналогии с характеристиками внешнепланарных и плоских графов как графов с инвариантом графа Колена де Вердьера не более двух или трех, встраиваемые без связей графы - это графы, у которых инвариант Колена де Вердьера не превышает четырех.

См. также

• Комбинаторное отображение - комбинаторный объект, который может кодировать плоские графы.
• Планаризация — плоский граф, сформированный из рисунка с пересечениями путем замены каждой точки пересечения новой вершиной.
• Толщина (теория графов) — наименьшее количество плоских графов, на которые можно разбить ребра данного графа.
• Planarity — компьютерная игра-головоломка, цель которой — встроить планарный граф в плоскость.
• Sprouts (игра) — игра с карандашом и бумагой, в которой в рамках игры строится планарный граф с определенными ограничениями.
• Задача о трёх коммунальных услугах , популярная головоломка

Ссылки

• Куратовский, Казимеж (1930), «К проблеме левых кривых в топологии» (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283 .
• Вагнер, К. (1937), «О свойстве плоских комплексов», Mathematical Annals (на немецком языке), 114 : 570–590, doi : 10.1007/BF01594196 , S2CID   123534907 .
• Бойер, Джон М.; Мирволд, Венди Дж. (2005), «На острие: упрощенная планарность O(n) путем сложения ребер» (PDF) , Journal of Graph Algorithms and Applications , 8 (3): 241–273, doi : 10.7155/jgaa .00091 .
• Маккей, Брендан ; Бринкманн, Гуннар, Полезный генератор планарных графов .
• де Фрейссе, Х.; Оссона де Мендес, П. ; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1029, arXiv : math/0610935 , doi : 10.1142/S0129054106004248 , S2CID   40107560 . Специальный выпуск по рисованию графов.
• Бадер, Д.А. ; Срешта, С. (1 октября 2003 г.). Новый параллельный алгоритм проверки планарности (технический отчет). Технический отчет UNM-ECE 03-002. Архивировано из оригинала 16 марта 2016 г.
• Фиск, Стив (1978), «Краткое доказательство теоремы Хватала о стороже», Журнал комбинаторной теории, серия B , 24 (3): 374, doi : 10.1016/0095-8956(78)90059-X .

Внешние ссылки

• Исходный код алгоритма планарности сложения ребер, версия 1.0 — бесплатный исходный код на C для эталонной реализации алгоритма планарности Бойера – Мирволда, который предоставляет как комбинаторное средство для плоского внедрения, так и изолятор подграфа Куратовского. Проект с открытым исходным кодом и бесплатной лицензией предоставляет алгоритмы планарности Edge Addition, текущую версию .
• Публичная реализация библиотеки и редактора графовых алгоритмов — библиотека графовых алгоритмов GPL, включая тестирование планарности, средство для внедрения планарности и выставку подграфов Куратовского в линейном времени.
• Инструменты библиотеки Boost Graph для плоских графов , включая тестирование планарности линейного времени, встраивание, изоляцию подграфов Куратовского и рисование прямых линий.
• 3 головоломки с утилитами и плоские графики
• Модель NetLogo Planarity — версия NetLogo игры Джона Тантало.