В теории графов планарный граф — это граф , который можно вложить в плоскость , т. е. его можно нарисовать на плоскости таким образом, что его ребра пересекаются только в своих конечных точках. Другими словами, его можно нарисовать так, чтобы никакие ребра не пересекались. [1] [2] Такой рисунок называется плоским графом или плоским вложением графа . Плоский граф можно определить как планарный граф с отображением каждого узла в точку на плоскости и каждого ребра в плоскую кривую на этой плоскости, так что крайними точками каждой кривой являются точки, отображаемые с ее конца. узлы, и все кривые не пересекаются, за исключением крайних точек.
Любой граф, который можно нарисовать на плоскости, можно нарисовать и на сфере , и наоборот, посредством стереографической проекции .
Плоские графы могут быть закодированы с помощью комбинаторных карт или систем вращения .
Класс эквивалентности топологически эквивалентных рисунков на сфере, обычно с дополнительными предположениями, такими как отсутствие перешейков , называется плоским отображением . Хотя плоский граф имеет внешнюю или неограниченную грань , ни одна из граней плоской карты не имеет определенного статуса.
Плоские графы обобщаются до графов, которые можно нарисовать на поверхности заданного рода . В этой терминологии плоские графы имеют род 0, поскольку плоскость (и сфера) являются поверхностями рода 0. Другие связанные темы см. в разделе « Встраивание графов ».
Польский математик Казимеж Куратовский дал характеристику плоских графов в терминах запрещенных графов , теперь известную как теорема Куратовского :
Подразделение графа происходит в результате вставки вершин в ребра (например, изменения ребра • —— • на • — • — • ) ноль или более раз.
Вместо рассмотрения подразделений теорема Вагнера касается миноров :
Минор графа получается в результате взятия подграфа и многократного стягивания ребра в вершину , при этом каждый сосед исходной конечной вершины становится соседом новой вершины.
Клаус Вагнер задал более общий вопрос, определяется ли какой-либо минорно-замкнутый класс графов конечным набором « запрещенных миноров ». Теперь это теорема Робертсона-Сеймура , доказанная в длинной серии статей. На языке этой теоремы K 5 и K 3,3 — запрещенные миноры для класса конечных плоских графов.
На практике сложно использовать критерий Куратовского, чтобы быстро решить, является ли данный граф плоским. Однако существуют быстрые алгоритмы решения этой задачи: для графа с n вершинами можно за время O ( n ) (линейное время) определить, может ли граф быть планарным или нет (см. Проверка планарности ).
Для простого связного плоского графа с v вершинами, e ребрами и f гранями при v ≥ 3 выполняются следующие простые условия :
В этом смысле планарные графы являются разреженными графами , поскольку они имеют только O ( v ) ребер, что асимптотически меньше максимального O ( v2 ) . Граф K3,3 , например, имеет 6 вершин, 9 ребер и ни одного цикла длины 3. Поэтому по теореме 2 он не может быть плоским . Эти теоремы обеспечивают необходимые условия планарности, которые не являются достаточными условиями, и поэтому могут использоваться только для доказательства того, что граф не планарен, а не то, что он планарен. Если обе теоремы 1 и 2 не работают, можно использовать другие методы.
Формула Эйлера гласит, что если конечный связный плоский граф нарисован на плоскости без каких-либо пересечений ребер, а v — количество вершин, e — количество ребер, а f — количество граней (областей, ограниченных ребрами, включая внешняя, бесконечно большая область), то
В качестве иллюстрации в приведенном выше графе-бабочке 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 :
Формула Эйлера справедлива и для выпуклых многогранников . Это не случайно: каждый выпуклый многогранник можно превратить в связный простой плоский граф, используя диаграмму Шлегеля многогранника — перспективную проекцию многогранника на плоскость с центром перспективы, выбранным вблизи центра одного из грани многогранника. Не каждый плоский граф таким образом соответствует выпуклому многограннику: например, деревья этого не делают. Теорема Стейница утверждает, что многогранные графы , образованные из выпуклых многогранников, представляют собой в точности конечные 3-связные простые планарные графы. В более общем смысле формула Эйлера применима к любому многограннику, грани которого представляют собой простые многоугольники , образующие поверхность, топологически эквивалентную сфере, независимо от ее выпуклости.
Связные плоские графы с более чем одним ребром подчиняются неравенству 2 e ≥ 3 f , поскольку каждая грань имеет как минимум три инцидентности ребер грани, и каждое ребро вносит ровно два инцидентности. Путем алгебраических преобразований этого неравенства с помощью формулы Эйлера v – e + f = 2 следует , что для конечных плоских графов средняя степень строго меньше 6. Графы с более высокой средней степенью не могут быть планарными.
Мы говорим, что две окружности, нарисованные на плоскости, целуются (или соприкасаются ) всякий раз, когда они пересекаются ровно в одной точке. «Граф монет» — это граф, образованный набором кругов, никакие два из которых не имеют перекрывающихся внутренних частей, путем создания вершины для каждого круга и ребра для каждой пары целующихся кругов. Теорема об упаковке кругов , впервые доказанная Полом Кебе в 1936 году, утверждает, что граф является плоским тогда и только тогда, когда он является графом монеты.
Этот результат обеспечивает простое доказательство теоремы Фари о том, что любой простой плоский граф можно вложить в плоскость таким образом, чтобы его ребра представляли собой отрезки прямых , не пересекающиеся друг с другом. Если поместить каждую вершину графа в центр соответствующего круга в представлении графа-монеты, то отрезки линий между центрами целующихся кругов не пересекают ни одно из других ребер.
Коэффициент связности или плотность D планарного графа или сети — это отношение числа f – 1 ограниченных граней (того же, что и схемный ранг графа по критерию планарности Мак Лейна ) к его максимально возможным значениям 2 v – 5 для графа с v вершинами:
Плотность подчиняется 0 ≤ D ≤ 1 , причем D = 0 для полностью разреженного планарного графа (дерева) и D = 1 для полностью плотного (максимального) планарного графа. [3]
Учитывая вложение G связного графа (не обязательно простого) в плоскость без пересечений ребер, мы строим двойственный граф G* следующим образом: мы выбираем по одной вершине в каждой грани G (включая внешнюю грань) и для каждого ребра e в G мы вводим новое ребро в G* , соединяющее две вершины в G* , соответствующие двум граням в G , которые встречаются в точке e . Более того, это ребро нарисовано так, что оно пересекает e ровно один раз и что никакое другое ребро G или G* не пересекается. Тогда G* снова является вложением (не обязательно простого) плоского графа; у него столько же ребер, сколько G , столько вершин, сколько G граней, и столько граней, сколько G имеет вершин. Термин «двойственный» оправдан тем, что G ** = G ; здесь равенство есть эквивалентность вложений на сфере . Если G — планарный граф, соответствующий выпуклому многограннику, то G* — плоский граф, соответствующий двойственному многограннику.
Дуальные графы полезны, поскольку многие свойства двойственного графа простыми способами связаны со свойствами исходного графа, что позволяет доказывать результаты о графах путем изучения их двойственных графов.
Хотя двойственный граф, построенный для конкретного вложения, уникален (с точностью до изоморфизма ), графы могут иметь разные (т.е. неизоморфные) двойственные графы, полученные из разных (т.е. негомеоморфных ) вложений.
Простой граф называется максимальным планарным, если он планарный, но добавление любого ребра (в данном множестве вершин) разрушит это свойство. Все грани (включая внешнюю) затем ограничиваются тремя краями, что объясняет альтернативный термин « триангуляция плоскости» . Альтернативные названия «треугольный граф» [4] или «триангулированный граф» [5] также использовались, но они неоднозначны, поскольку они чаще относятся к линейному графу полного графа и к хордальным графам соответственно. Любой максимальный планарный граф не менее чем 3-связен.
Если максимальный планарный граф имеет v вершин с v > 2 , то он имеет ровно 3 v – 6 ребер и 2 v – 4 грани.
Аполлоновы сети — это максимальные планарные графы, образованные путем многократного разделения треугольных граней на тройки меньших треугольников. Эквивалентно, это плоские 3-деревья .
Ущемленные графы — это графы, в которых каждый периферийный цикл представляет собой треугольник. В максимальном планарном графе (или, в более общем плане, в многогранном графе) периферийные циклы являются гранями, поэтому максимальные планарные графы задушены. Удушенные графы включают также хордальные графы и представляют собой именно те графы, которые могут быть образованы клик-суммами (без удаления ребер) полных графов и максимальных планарных графов. [6]
Внепланарные графы — это графы с вложением в плоскость, все вершины которого принадлежат неограниченной грани вложения. Каждый внешнепланарный граф планарен, но обратное неверно: K 4 планарен, но не внешнепланарен. Теорема, подобная теореме Куратовского, утверждает, что конечный граф является внешнепланарным тогда и только тогда, когда он не содержит подразделений K 4 или K 2,3 . Вышесказанное является прямым следствием того факта, что граф G является внешнепланарным, если граф, образованный из G добавлением новой вершины с ребрами, соединяющими его со всеми остальными вершинами, является плоским графом. [7]
1-внепланарное вложение графа аналогично внешнепланарному вложению. При k > 1 плоское вложение называется k -внепланарным, если удаление вершин на внешней грани приводит к ( k – 1) -внепланарному вложению. Граф называется k -внепланарным, если он имеет k -внепланарное вложение.
Граф Халина — это граф, сформированный из неориентированного плоского дерева (без узлов степени два) путем соединения его листьев в цикл в порядке, заданном плоским вложением дерева. Эквивалентно, это многогранный граф , в котором одна грань примыкает ко всем остальным. Каждый граф Халина планарен. Как и внешнепланарные графы, графы Халина имеют малую ширину дерева , что упрощает решение многих алгоритмических задач, чем в неограниченных плоских графах. [8]
Планарный граф, направленный вверх, — это направленный ациклический граф , который можно нарисовать на плоскости, ребра которого представляют собой непересекающиеся кривые, последовательно ориентированные вверх. Не каждый планарный направленный ациклический граф является планарным вверх, и NP-полной является проверка того, является ли данный граф планарным вверх.
Планарный граф называется выпуклым , если все его грани (включая внешнюю) являются выпуклыми многоугольниками . Не все плоские графы имеют выпуклое вложение (например, полный двудольный граф K 2,4 ). Достаточным условием того, что граф может быть нарисован выпуклым, является то, что он является подразделением планарного графа , связанного с 3 вершинами . Пружинная теорема Тутте даже утверждает, что для простых плоских графов, связанных с 3 вершинами, положение внутренних вершин может быть выбрано как среднее значение его соседей.
Представленные в слове плоские графы включают плоские графы без треугольников и, в более общем плане, 3-раскрашиваемые плоские графы, [9] , а также определенные подразделения граней графов с треугольной сеткой, [10] и некоторые триангуляции цилиндрических графов, покрытых сеткой. [11]
Асимптотика числа (помеченных) плоских графов на вершинах равна , где и . [12]
Почти все планарные графы имеют экспоненциальное число автоморфизмов. [13]
Число непомеченных (неизоморфных) плоских графов на вершинах находится между и . [14]
Теорема о четырёх цветах утверждает, что каждый плоский граф раскрашивается в 4 цвета (т.е. 4-дольный).
Теорема Фари утверждает, что каждый простой плоский граф допускает представление в виде плоского прямолинейного графа . Универсальный набор точек — это набор точек, такой, что каждый плоский граф с n вершинами имеет такое вложение со всеми вершинами в наборе точек; существуют универсальные множества точек квадратичного размера, образованные взятием прямоугольного подмножества целочисленной решетки . Каждый простой внешнепланарный граф допускает такое вложение в плоскость, что все вершины лежат на фиксированной окружности, а все ребра представляют собой отрезки прямых, лежащие внутри диска и не пересекающиеся, поэтому правильные многоугольники с n -вершинами универсальны для внешнепланарных графов.
Гипотеза Шейнермана (теперь теорема) утверждает, что каждый плоский граф можно представить как граф пересечений отрезков прямой на плоскости.
Теорема о плоском сепараторе утверждает, что каждый планарный граф с n -вершинами можно разделить на два подграфа размером не более 2 n /3 удалением O( √ n ) вершин. Как следствие, плоские графы также имеют ширину дерева и ширину ветвей O( √ n ).
Теорема о структуре плоского произведения утверждает, что каждый планарный граф является подграфом произведения сильного графа графа с шириной дерева не более 8 и пути. [15] Этот результат был использован, чтобы показать, что плоские графы имеют ограниченное число очередей , ограниченное неповторяющееся хроматическое число и универсальные графы почти линейного размера. Он также имеет приложения для ранжирования вершин [16] и p -центрированной раскраски [17] планарных графов.
Для двух плоских графов с v вершинами можно за время O( v ) определить, изоморфны они или нет (см. также проблему изоморфизма графов ). [18]
Любой планарный граф на n узлах имеет не более 8 (n-2) максимальных клик, [19] из чего следует, что класс плоских графов является классом с небольшим количеством клик.
Вершинный граф — это граф, который можно сделать плоским, удалив одну вершину, а k -верхний граф — это граф, который можно сделать плоским, удалив не более k вершин.
1 -планарный граф — это граф, который можно нарисовать на плоскости не более чем с одним простым пересечением на каждое ребро, а k -планарный граф — это граф, который можно нарисовать не более чем с k простыми пересечениями на каждое ребро.
Граф карты — это граф, сформированный из набора конечного числа односвязных внутренних непересекающихся областей на плоскости путем соединения двух областей, когда они имеют хотя бы одну общую граничную точку. Когда не более трех регионов встречаются в одной точке, результатом является плоский граф, но когда четыре или более регионов встречаются в одной точке, результат может быть неплоским (например, если представить круг, разделенный на сектора, с секторами поскольку это регионы, то соответствующий граф карты является полным графом, поскольку все сектора имеют общую граничную точку — центральную точку).
Тороидальный граф — это граф, который можно вложить без пересечений на торе . В более общем смысле, род графа — это минимальный род двумерной поверхности, в которую граф может быть вложен; плоские графы имеют род ноль, а неплоские тороидальные графы имеют род один. Каждый граф можно без пересечений вложить в некоторую (ориентируемую, связную) замкнутую двумерную поверхность (сферу с ручками), и, таким образом, род графа корректно определен. Очевидно, что если граф можно вложить без пересечений в (ориентируемую, связную, замкнутую) поверхность рода g, то его можно вложить без пересечений во все (ориентируемые, связные, замкнутые) поверхности большего или равного рода. В теории графов есть и другие понятия, которые называются «родом X» с некоторым квалификатором «X»; в целом они отличаются от определенного выше понятия «род» без каких-либо определителей. В частности, неориентируемый род графа (с использованием неориентируемых поверхностей в его определении) для общего графа отличается от рода этого графа (с использованием ориентируемых поверхностей в его определении).
Любой граф можно вложить в трехмерное пространство без пересечений. Фактически, любой граф можно нарисовать без пересечений в схеме с двумя плоскостями, где две плоскости расположены друг над другом, а ребрам разрешено «подпрыгивать вверх» и «падать вниз» из одной плоскости в другую в любом месте. (не только в вершинах графа), чтобы ребра могли избегать пересечений с другими ребрами. Это можно интерпретировать как утверждение, что можно создать любую электрическую проводящую сеть с помощью двусторонней печатной платы , где может быть выполнено электрическое соединение между сторонами платы (как это возможно в случае типичных реальных печатных плат, с электрическими соединениями на верхней стороне платы обеспечивается кусками провода, а на нижней стороне - медными дорожками, встроенными в саму плату, а электрическое соединение между сторонами платы достигается путем сверления отверстий, пропускания проводов через отверстия и их пайки . в рельсы); это также можно интерпретировать как утверждение, что для построения любой дорожной сети нужны только мосты или только туннели, а не то и другое (достаточно 2 уровней, 3 не нужны). Также в трехмерном пространстве тривиален вопрос о построении графа без пересечений. Однако трехмерный аналог плоских графов представляют собой бессвязно встраиваемые графы , графы, которые можно встроить в трехмерное пространство таким образом, что никакие два цикла не будут топологически связаны друг с другом. По аналогии с характеристиками Куратовского и Вагнера плоских графов как графов, которые не содержат K 5 или K 3,3 в качестве минора, бессвязно встраиваемые графы могут быть охарактеризованы как графы, которые не содержат в качестве минора ни одного из семь графов в семье Петерсенов . По аналогии с характеристиками внешнепланарных и плоских графов как графов с инвариантом графа Колена де Вердьера не более двух или трех, встраиваемые без связей графы - это графы, у которых инвариант Колена де Вердьера не превышает четырех.
Таким образом, плоский граф, нарисованный на плоской поверхности, либо не имеет пересечений ребер, либо может быть перерисован без них.