Плоский граф

Плоский граф

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины это точки плоскости, а ребра линии на ней, области, на которые граф разбивает поверхность называются гранями. Плоский граф — граф уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.

Содержание

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

K5, полный граф с 5 вершинами
K3,3, граф, иллюстрирующий задачу о трех колодцах
  • достаточное условие — если граф содержит двудольный подграф K3,3 или полный подграф K5, то он является не планарным;
  • необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

Теорема Понтрягина-Куратовского

Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.

  • Вариант

Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.

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

Для связного плоского графа справедливо следующее соотношение между количеством вершин V, ребер E и граней F:

V − E + F = 2

Оно было найдено Эйлером в 1736 г.[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум.

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

E \le 3V-6

то есть, при большем числе ребер граф заведомо непланарен. (Обратное утверждение не верно, пример.) Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Планарные графы в задачах

Задача о трех колодцах. Есть три дома и три колодца. Доказать, что невозможно так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. (Мосты строить нельзя.)

Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны имеющий общий участок границы имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырех красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.

См. также

Примечания

  1. ↑ Ф. Харари Теория графов УРСС стр. 126

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Плоский граф" в других словарях:

  • плоский граф — планарный граф — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы планарный граф EN flat graph …   Справочник технического переводчика

  • ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… …   Математическая энциклопедия

  • ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… …   Математическая энциклопедия

  • ГРАФ — множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,… …   Математическая энциклопедия

  • ГРАФ ДВУДОЛЬНЫЙ — бихроматический граф, граф, множество вершин к рого можно разбить на два непересекающихся подмножества и , (т …   Математическая энциклопедия

  • Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф …   Википедия

  • Планарный граф — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим …   Википедия

  • Ламанов граф — В теории графов Ламановым графом с n вершинами называют такой граф G, что, во первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во вторых, граф G имеет ровно 2n −3 ребра. Ламановы графы …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»