Планарный граф
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения ребер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.
Содержание
Простейшие свойства плоских графов
Формула Эйлера
Для связного плоского графа справедливо следующее соотношение между количеством вершин <math>|V(G)|</math>, рёбер <math>|E(G)|</math> и граней <math>|F(G)|</math> (включая внешнюю грань):
- <math>\ |V(G)|-|E(G)|+|F(G)| = 2.</math>
Оно было найдено Эйлером в 1736 г.[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум, а, например, для поверхности тора — нулю.
Формула имеет множество полезных следствий. Во-первых, все плоские укладки одного графа имеют одинаковое количество граней. Во-вторых, если каждая грань ограничена не менее чем тремя рёбрами (при условии, что в графе больше двух рёбер), а каждое ребро разделяет две грани, то
- <math>3|F(G)| \le 2|E(G)|,</math>
следовательно,
- <math>|E(G)| \le 3|V(G)|-6,</math>
то есть, при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение не верно: в качестве контрпримера можно взять граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.
Общая формула также легко обобщается на случай несвязного графа:
- <math>|V(G)|-|E(G)|+|F(G)|=1+|C(G)|,</math>
где <math>|C(G)|</math> — количество компонент связности в графе.
Два примера непланарных графов
Полный граф с пятью вершинами
Лемма. Полный граф с пятью вершинами (К5) нельзя уложить на плоскость.
Доказательство. Для него не выполняется <math>E \leqslant 3V - 6</math>.
«Домики и колодцы»
Задача о трёх колодцах. Есть три дома и три колодца. Можно ли так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. Мосты строить нельзя.
Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К3,3) нельзя уложить на плоскость.
Доказательство. По формуле Эйлера граф имеет 5 граней.
С другой стороны: любая грань (включая внешнюю) содержит не менее 4 рёбер. Поскольку каждое ребро включается в ровно две грани, получается соотношение <math>4F \leqslant 2E</math>, F — количество граней, E — количество рёбер. Подставляем в это неравенство F = 5 и E = 9 и видим, что оно не выполняется.
Теорема Понтрягина — Куратовского
Очевидно утверждение: если граф G содержит подграф, гомеоморфный K5 или K3,3, то его невозможно разложить на плоскости. Оказывается, верно и обратное.
|
Теорему также можно сформулировать в следующем варианте (иногда его называют «теорема Вагнера»).
|
Компьютерная проверка на планарность
Первый алгоритм, отыскивающий подграф Куратовского за линейное время, разработан в 1974 году Хопкрофтом и Тарьяном.[2]
Признаки непланарных графов
- достаточное условие — если граф содержит полный двудольный подграф K3,3 или полный подграф K5, то он является непланарным;
- необходимое условие — если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.
Планарные графы в задачах
Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны, имеющие общий участок границы, имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырёх красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.
Спрямление графа (теорема Фари). Любой плоский граф можно перерисовать так, чтобы он остался плоским, а рёбра стали отрезками прямых.
Обобщения
Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины — это точки поверхности, а рёбра — линии на ней. Области, на которые граф разбивает поверхность, называются гранями. Плоский граф — граф, уложенный на плоскость.
См. также
- Словарь терминов теории графов
- Теория графов
- Клетка (теория графов)
- Теорема Фари
- Гамма-алгоритм — алгоритм проверки графа на планарность и его плоской укладки
Напишите отзыв о статье "Планарный граф"
Примечания
- ↑ Харари Ф. Теория графов УРСС стр. 126
- ↑ Hopcroft, John & Tarjan, Robert E. (1974), "[dx.doi.org/10.1145%2F321850.321852 Efficient planarity testing]", Journal of the Association for Computing Machinery Т. 21 (4): 549–568, DOI 10.1145/321850.321852.
Ссылки
- [compscicenter.ru/program/lecture/6702 Видеолекция, посвящённая планарным графам]
- А. Ю. Ольшанский. [window.edu.ru/window_catalog/redir?id=20742&file=9611_117.pdf Плоские графы], СОЖ, 1996, No 11, с. 117—122.
- Харари Ф.. Теория графов. М.: «Мир». 1973
- [rain.ifmo.ru/cat/view.php/theory/list Дискретная математика: Алгоритмы, визуализация графов, апплеты]
Отрывок, характеризующий Планарный граф
Была одна из тех мартовских ночей, когда зима как будто хочет взять свое и высыпает с отчаянной злобой свои последние снега и бураны. Навстречу немца доктора из Москвы, которого ждали каждую минуту и за которым была выслана подстава на большую дорогу, к повороту на проселок, были высланы верховые с фонарями, чтобы проводить его по ухабам и зажорам.
Княжна Марья уже давно оставила книгу: она сидела молча, устремив лучистые глаза на сморщенное, до малейших подробностей знакомое, лицо няни: на прядку седых волос, выбившуюся из под платка, на висящий мешочек кожи под подбородком.
Няня Савишна, с чулком в руках, тихим голосом рассказывала, сама не слыша и не понимая своих слов, сотни раз рассказанное о том, как покойница княгиня в Кишиневе рожала княжну Марью, с крестьянской бабой молдаванкой, вместо бабушки.
– Бог помилует, никогда дохтура не нужны, – говорила она. Вдруг порыв ветра налег на одну из выставленных рам комнаты (по воле князя всегда с жаворонками выставлялось по одной раме в каждой комнате) и, отбив плохо задвинутую задвижку, затрепал штофной гардиной, и пахнув холодом, снегом, задул свечу. Княжна Марья вздрогнула; няня, положив чулок, подошла к окну и высунувшись стала ловить откинутую раму. Холодный ветер трепал концами ее платка и седыми, выбившимися прядями волос.
– Княжна, матушка, едут по прешпекту кто то! – сказала она, держа раму и не затворяя ее. – С фонарями, должно, дохтур…
– Ах Боже мой! Слава Богу! – сказала княжна Марья, – надо пойти встретить его: он не знает по русски.
Княжна Марья накинула шаль и побежала навстречу ехавшим. Когда она проходила переднюю, она в окно видела, что какой то экипаж и фонари стояли у подъезда. Она вышла на лестницу. На столбике перил стояла сальная свеча и текла от ветра. Официант Филипп, с испуганным лицом и с другой свечей в руке, стоял ниже, на первой площадке лестницы. Еще пониже, за поворотом, по лестнице, слышны были подвигавшиеся шаги в теплых сапогах. И какой то знакомый, как показалось княжне Марье, голос, говорил что то.
– Слава Богу! – сказал голос. – А батюшка?
– Почивать легли, – отвечал голос дворецкого Демьяна, бывшего уже внизу.
Потом еще что то сказал голос, что то ответил Демьян, и шаги в теплых сапогах стали быстрее приближаться по невидному повороту лестницы. «Это Андрей! – подумала княжна Марья. Нет, это не может быть, это было бы слишком необыкновенно», подумала она, и в ту же минуту, как она думала это, на площадке, на которой стоял официант со свечой, показались лицо и фигура князя Андрея в шубе с воротником, обсыпанным снегом. Да, это был он, но бледный и худой, и с измененным, странно смягченным, но тревожным выражением лица. Он вошел на лестницу и обнял сестру.
– Вы не получили моего письма? – спросил он, и не дожидаясь ответа, которого бы он и не получил, потому что княжна не могла говорить, он вернулся, и с акушером, который вошел вслед за ним (он съехался с ним на последней станции), быстрыми шагами опять вошел на лестницу и опять обнял сестру. – Какая судьба! – проговорил он, – Маша милая – и, скинув шубу и сапоги, пошел на половину княгини.
Маленькая княгиня лежала на подушках, в белом чепчике. (Страдания только что отпустили ее.) Черные волосы прядями вились у ее воспаленных, вспотевших щек; румяный, прелестный ротик с губкой, покрытой черными волосиками, был раскрыт, и она радостно улыбалась. Князь Андрей вошел в комнату и остановился перед ней, у изножья дивана, на котором она лежала. Блестящие глаза, смотревшие детски, испуганно и взволнованно, остановились на нем, не изменяя выражения. «Я вас всех люблю, я никому зла не делала, за что я страдаю? помогите мне», говорило ее выражение. Она видела мужа, но не понимала значения его появления теперь перед нею. Князь Андрей обошел диван и в лоб поцеловал ее.
– Душенька моя, – сказал он: слово, которое никогда не говорил ей. – Бог милостив. – Она вопросительно, детски укоризненно посмотрела на него.
– Я от тебя ждала помощи, и ничего, ничего, и ты тоже! – сказали ее глаза. Она не удивилась, что он приехал; она не поняла того, что он приехал. Его приезд не имел никакого отношения до ее страданий и облегчения их. Муки вновь начались, и Марья Богдановна посоветовала князю Андрею выйти из комнаты.
Акушер вошел в комнату. Князь Андрей вышел и, встретив княжну Марью, опять подошел к ней. Они шопотом заговорили, но всякую минуту разговор замолкал. Они ждали и прислушивались.
– Allez, mon ami, [Иди, мой друг,] – сказала княжна Марья. Князь Андрей опять пошел к жене, и в соседней комнате сел дожидаясь. Какая то женщина вышла из ее комнаты с испуганным лицом и смутилась, увидав князя Андрея. Он закрыл лицо руками и просидел так несколько минут. Жалкие, беспомощно животные стоны слышались из за двери. Князь Андрей встал, подошел к двери и хотел отворить ее. Дверь держал кто то.
– Нельзя, нельзя! – проговорил оттуда испуганный голос. – Он стал ходить по комнате. Крики замолкли, еще прошло несколько секунд. Вдруг страшный крик – не ее крик, она не могла так кричать, – раздался в соседней комнате. Князь Андрей подбежал к двери; крик замолк, послышался крик ребенка.
«Зачем принесли туда ребенка? подумал в первую секунду князь Андрей. Ребенок? Какой?… Зачем там ребенок? Или это родился ребенок?» Когда он вдруг понял всё радостное значение этого крика, слезы задушили его, и он, облокотившись обеими руками на подоконник, всхлипывая, заплакал, как плачут дети. Дверь отворилась. Доктор, с засученными рукавами рубашки, без сюртука, бледный и с трясущейся челюстью, вышел из комнаты. Князь Андрей обратился к нему, но доктор растерянно взглянул на него и, ни слова не сказав, прошел мимо. Женщина выбежала и, увидав князя Андрея, замялась на пороге. Он вошел в комнату жены. Она мертвая лежала в том же положении, в котором он видел ее пять минут тому назад, и то же выражение, несмотря на остановившиеся глаза и на бледность щек, было на этом прелестном, детском личике с губкой, покрытой черными волосиками.
