27-04-2024
Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.
Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины — это точки плоскости, а ребра — линии на ней. Области, на которые граф разбивает поверхность, называются гранями. Плоский граф — граф, уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.
Содержание |
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.
Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.
Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань):
Оно было найдено Эйлером в 1736 г.[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум. Формула имеет множество полезных следствий. Из того, что каждая грань ограничена не менее чем тремя ребрами (при условии, что в графе больше двух ребер), а каждое ребро разделяет две грани
следует, что для плоского графа
то есть, при большем числе ребер граф заведомо непланарен. Обратное утверждение не верно, например, граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.
Задача о трех колодцах. Есть три дома и три колодца. Доказать, что невозможно так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. (Мосты строить нельзя.)
Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны, имеющие общий участок границы, имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырех красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Планарный граф содержит 12 вершин степени 3 сколько у этого графа ребер и граней, планарный граф, планарный граф условие.
Участник:Anti-conformist/Черновик-4, Файл:Museum in Berezova Luka.JPG, Файл:15-03-2014-Salon de Genève 2014-Twingo III (1).jpg, Сань Мао, Файл:Streetfiles nomad-obs-basf-sm365.jpg.