Русская Википедия:1-планарный граф

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:3-crossing Heawood graph.svg
1-планарный рисунок графа Хивуда — шесть рёбер имеют единичные пересечения, а остальные 15 рёбер не пересекаются.

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

Раскраска

1-планарные графы первым рассматривал Рингель, который показал, что они могут быть раскрашены, не превышая семи цветовШаблон:Sfn. Позднее точное число цветов, необходимых для раскраски этих графов, (в худшем случае) было уменьшено до шестиШаблон:Sfn. Пример полного графа K6, являющегося 1-планарным, показывает, что 1-планарные графы иногда могут требовать для раскраски шести цветов. Однако доказательство достаточности шести цветом не является простым.

Файл:Prism-vf-color.svg
Раскраска вершин и граней треугольной призмы требует шесть цветов

Поводом для рассмотрения 1-планарных графов Рингелем была попытка решить вариант задачи тотальной раскраски для планарных графов, в которой раскрашиваются вершины и грани планарного графа таким образом, что никакие две смежные вершины не имеют одинаковый цвет и любые две смежные грани тоже должны быть раскрашены в разные цвета, а также цвета вершин и смежных им граней должны отличаться. Очевидно, что это можно сделать с помощью восьми красок, если применить теорему о четырёх красках для графа и его двойственного графа раздельно, применив два непересекающихся набора четырёх красок. Однако можно получить меньшее количество красок, если сформировать вспомогательный граф, имеющий по вершине для каждой вершины и грани исходного планарного графа, и в котором две вершины вспомогательного графа смежны, если они соответствуют смежным объектам заданного планарного графа. Раскраска вершин вспомогательного графа соответствует раскраске исходного планарного графа. Вспомогательный граф является 1-планарным, откуда следует, что задача Рингеля раскраски вершин и граней может быть решена с использованием шести цветовШаблон:Sfn. Граф K6 не может быть получен как вспомогательный граф таким образом, но, тем не менее, задача раскраски вершин и граней иногда требует шести цветов. Например, если раскрашивать планарный граф треугольной призмы, её 6 вершин + 5 граней требует шести цветовШаблон:Sfn.

Плотность рёбер

Любой 1-планарный граф с n вершинами имеет не более 4n − 8 рёберШаблон:Sfn. Более строго, каждый рисунок 1-планарного графа имеет не более n − 2 пересечений. Удаление одного ребра из каждой пересекающейся пары рёбер оставляет планарный граф, который имеет не более 3n − 6 рёбер, откуда немедленно следует граница числа рёбер 4n − 8 исходного 1-планарного графаШаблон:Sfn. Однако, в отличие от планарных графов (для которых все максимальные планарные графы на заданном множестве вершин имеют одинаковое число рёбер), существуют максимальные 1-планарные графы (графы, в которые нельзя добавить ребро с сохранением 1-планарности), которые имеют существенно менее 4n − 8 рёберШаблон:Sfn. Граница 4n − 8 максимального возможного числа рёбер в 1-планарном графе может быть использована, чтобы показать, что полный граф K7 с семью вершинами не является 1-планарным, поскольку этот граф имеет 21 ребро, а тогда 4n − 8 = 20 < 21 Шаблон:Sfn.

Говорят, что 1-планарный граф является оптимальным 1-планарным графом, если он имеет в точности 4n − 8 рёбер, максимально возможное число. В 1-планарном вложении оптимального 1-планарного графа непересекающиеся рёбра обязательно образуют разбиение на четырёхугольники (т.е. образуют полиэдральный граф, в котором каждая грань является четырёхугольником). Любое разбиение на четырёхугольники порождает 1-планарный граф путём добавления двух диагоналей в каждую квадратную грань. Отсюда следует, что любой оптимальный 1-планарный граф является эйлеровым (все его вершины имеют чётную степень), что наименьшая степень в таких графах — 6, и что любой оптимальный 1-планарный граф имеет по меньшей мере восемь вершин со степенью в точности шесть. Кроме того, любой оптимальный 1-планарный граф вершинно 4-связен и любое 4-вершинное сечение в таком графе является отсекающим циклом в нижележащем разбиении на четырёхугольникиШаблон:Sfn.

Графы, имеющие прямолинейные 1-планарные рисунки (то есть рисунки, в которых каждое ребро представляется прямолинейным отрезком и каждый отрезок пересекается максимум одним другим ребром), имеют слегка более сильную границу 4n − 9 максимального числа рёбер, которая достигается на бесконечном числе графовШаблон:Sfn.

Полные многодольные графы

Файл:1planar-K2222.svg
1-планарный рисунок графа коктейль-вечеринки K2,2,2,2

Полная классификация 1-планарных полных графов, полных двудольных графов и более общих полных многодольных графов известна. Любой полный двудольный граф вида K2,n является 1-планарным, как и любой полный трёхдольный граф вида K1,1,n. Кроме этих бесконечных множеств, полными многодольными 1-планарными графами являются K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2 и их подграфы. Минимальные полные многодольные графы, не являющиеся 1-планарными, — это K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. Например, полный двудольный граф K3,6 является 1-планарным, поскольку он является подграфом K1,1,1,6, а вот K3,7 не является 1-планарнымШаблон:Sfn.

Вычислительная сложность

Проверка, является ли граф 1-планарным, NP-полнаШаблон:SfnШаблон:Sfn, и задача остаётся NP-полной даже для графов, полученных из планарных графов путём добавления единственного ребраШаблон:Sfn и для графов ограниченной Шаблон:Не переведено 5Шаблон:Sfn.

Задача Шаблон:Не переведено 5, если параметризовать по цикломатическому числу или по глубине дерева, так что она может быть решена за полиномиальное время, если эти параметры ограниченыШаблон:Sfn.

В отличие от теоремы Фари для планарных графов, не все 1-планарные графы могут быть нарисованы 1-планарно с отрезками прямой в качестве рёберШаблон:SfnШаблон:Sfn. Однако проверка, можно ли нарисовать 1-планарный граф с прямыми рёбрами, может быть выполнена за полиномиальное времяШаблон:Sfn. Кроме того, любой вершинно 3-связный 1-планарный граф имеет 1-планарный рисунок, в котором максимум одно ребро на внешней грани имеет излом. Такой рисунок может быть построен за линейное время, исходя из 1-планарного вложения графаШаблон:Sfn. 1-планарные графы имеют ограниченную книжную толщинуШаблон:Sfn, но некоторые 1-планарные графы, включая K2,2,2,2, имеют книжную толщину по меньшей мере четыреШаблон:Sfn.

1-планарные графы имеют ограниченную локальную древесную ширину, что означает, что существует (линейная) функция f, такая, что 1-планарные графы диаметра d имеют древесную ширину, не превосходящую f(d). То же свойство имеет место для более общих графов, которые можно вложить в поверхность ограниченного рода с ограниченным числом пересечений на ребро. Они также имеют сепараторы, небольшое множество вершин, удаление которых разбивает граф на связные компоненты, размер которых составляет постоянную дробную часть от всего графа. Опираясь на эти свойства многочисленные алгоритмы для планарных графов, такие как техника Бренды Бейкер (Brenda Sue Baker – американская женщина-математик ) для построения аппроксимационных алгоритмов, могут быть расширены для 1-планарных графов. Например, этот метод приводит к приближенной схеме полиномиального времени для нахождения наибольшего независимого множества 1-планарного графа[1].

Обобщения и связанные концепции

Класс графов, аналогичных внешнепланарным графам для 1-планарности, называется внешне 1-планарные графы. Это графы, которые можно нарисовать на диске с вершинами на границе диска и с рёбрами, имеющими максимум одно пересечение на ребро. Эти графы всегда могут быть нарисованы (в виде внешне 1-планарного графа) с прямыми рёбрами и пересечениями под прямыми угламиШаблон:Sfn. При помощи динамического программирования на SPQR-дереве заданного графа можно проверить, не является ли граф внешне 1-планарным, за линейное времяШаблон:SfnШаблон:Sfn. Трёхсвязные компоненты графа (узлы дерева SPQR) могут состоять только из циклов, бондграфов и полных графов с четырьмя вершинами, откуда следует, что внешне 1-планарные графы являются планарными и имеют древесную ширину максимум три. В отличие от 1-планарных графов, внешне 1-планарные графы имеют характеризацию в терминах миноров графа — граф является внешне 1-планарным тогда и только тогда, когда в нём нет ни одного из пяти запрещённых миноровШаблон:Sfn.

Классу 1-планарных графов принадлежат Шаблон:Не переведено 5, графы, образованные из смежных регионов плоскости с условием, что никакая точка не лежит на границе более четырёх регионов (вершины (регионы) соединены ребром, если регионы граничат). И обратно — любой оптимальный 1-планарный граф является графом 4-карты. Однако 1-планарные графы, не являющиеся оптимальными 1-планарными, могут и не быть графами картШаблон:Sfn.

1-планарные графы обобщаются до k-планарных графов, в которых каждое ребро пересекается другими рёбрами не более k раз. Рингель определил локальное число пересечений графа G как наименьшее неотрицательное k, такое, что G имеет k-планарный рисунок. Поскольку локальное число пересечений равно наибольшей степени графа пересечений рёбер оптимального рисунка, а толщина (минимальное число планарных графов, на которые можно разложить рёбра) может рассматриваться как хроматическое число графа пересечений подходящего рисунка, из теоремы Брукса следует, что толщина не больше чем на единицу превышает локальное число пересеченийШаблон:Sfn. k-планарные графы с n вершинами имеют максимум O(k1/2n) рёберШаблон:Sfn и древесную ширину O((kn)1/2)Шаблон:Sfn. Неглубокий минор k-планарного графа с глубиной d сам является (2d + 1)k-планарным, так что неглубокие миноры 1-планарных графов и k-планарных графов являются разреженными графами, здесь имеется в виду, что 1-планарные и k-планарные графы имеют Шаблон:Не переведено 5Шаблон:Sfn.

Для непланарных графов также можно задать параметр число пересечений, минимальное число рёбер, которые пересекаются в любом рисунке графа. Граф с числом пересечений k обязательно k-планарен, но обратное не обязательно верно. Например, Граф Хивуда имеет число пересечений 3, но не обязательно эти пересечения должны быть с одним ребром, он 1-планарен и может быть нарисован с одновременной опримизацией общего числа пересечений и пересечений на одно ребро.

Другое связанное понятие для непланарных графов — Шаблон:Не переведено 5, минимальное число рёбер, которые нужно удалить, чтобы сделать граф планарным.

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvnb. Григорьев и Бодлаендер формулировали свои результаты для графов с известным 1-планарным вложением и использовали древесное разложение вложения с пересечениями, заменёнными на вершины степени четыре. Однако их методы напрямую могут быть применены для исходного 1-планарного графа с ограниченной локальной древесной шириной, что позволяет применить метод Бейкер к ним прямо, не зная заранее вложения.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:1-планарный_граф&oldid=8525624