Что такое плоский граф
Плоский граф
Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.
Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины это точки плоскости, а ребра линии на ней, области, на которые граф разбивает поверхность называются гранями. Плоский граф — граф уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.
Содержание
Критерий непланарности
Теорема Понтрягина-Куратовского
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.
Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.
Формула Эйлера
Для связного плоского графа справедливо следующее соотношение между количеством вершин V, ребер E и граней F:
Оно было найдено Эйлером в 1736 г. [1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум.
Формула имеет множество полезных следствий. Из того, что каждая грань ограничена не более чем тремя ребрами, следует, что для плоского графа
то есть, при большем числе ребер граф заведомо непланарен. (Обратное утверждение не верно, пример.) Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.
Планарные графы в задачах
Задача о трех колодцах. Есть три дома и три колодца. Доказать, что невозможно так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. (Мосты строить нельзя.)
Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны имеющий общий участок границы имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырех красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.
См. также
Примечания
Ссылки
Полезное
Смотреть что такое «Плоский граф» в других словарях:
плоский граф — планарный граф — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы планарный граф EN flat graph … Справочник технического переводчика
ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия
ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Планарный граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия
Ламанов граф — В теории графов Ламановым графом с n вершинами называют такой граф G, что, во первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во вторых, граф G имеет ровно 2n −3 ребра. Ламановы графы … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
ГРАФ ПЛОСКИЙ
В теории графов большое внимание уделяется раскраскам Г. п. (см. Графа раскраска);для неплоских графов изучаются различные числовые характеристики, показывающие степень непланарности, напр, род, толщина, крупность графа, число скрещиваний и др. (см. Графа укладка).
Лит.:[1]Харари Ф., Теория графов, пер. с англ. М., 1973. В. Б. Алексеев.
Полезное
Смотреть что такое «ГРАФ ПЛОСКИЙ» в других словарях:
ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия
плоский граф — планарный граф — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы планарный граф EN flat graph … Справочник технического переводчика
Плоский граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Планарный граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия
Ламанов граф — В теории графов Ламановым графом с n вершинами называют такой граф G, что, во первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во вторых, граф G имеет ровно 2n −3 ребра. Ламановы графы … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
СОДЕРЖАНИЕ
Теоремы Куратовского и Вагнера
Вместо того, чтобы рассматривать подразделения, теорема Вагнера имеет дело с несовершеннолетними :
Минор графа результатов принимать подграф и неоднократно стягивание края в вершину, с каждым соседом исходных конечных вершин становится соседом новой вершины.
Другие критерии планарности
На практике трудно использовать критерий Куратовского, чтобы быстро решить, является ли данный граф плоским. Однако существуют быстрые алгоритмы решения этой проблемы: для графа с n вершинами можно определить за время O ( n ) (линейное время), может ли граф быть плоским или нет (см. Проверка планарности ).
Для простого связного плоского графа с v вершинами, e ребрами и f гранями для v ≥ 3 выполняются следующие простые условия :
Формула Эйлера
Средняя степень
Графики монет
Плотность планарного графика
Связанные семейства графов
Максимальные плоские графы
Внешнепланарные графы
Графики Халина
Другие родственные семьи
Перечисление планарных графов
Почти все плоские графы имеют экспоненциальное число автоморфизмов.
Другие факты и определения
Теорема о четырех цветах утверждает, что каждый планарный граф можно раскрашивать в четыре цвета (т. Е. С четырьмя частями).
Двойственные полезны, потому что многие свойства двойственного графа связаны простыми способами со свойствами исходного графа, что позволяет доказывать результаты о графах, исследуя их двойственные графы.
Хотя дуальный, построенный для конкретного вложения, уникален (с точностью до изоморфизма ), графы могут иметь разные (т. Е. Неизоморфные) дуальные, полученные из разных (т. Е. Негомеоморфных ) вложений.
Теорема о плоском разделителе утверждает, что любой планарный граф с n вершинами можно разбить на два подграфа размером не более 2 n / 3 путем удаления O ( √ n ) вершин. Как следствие, планарные графы также имеют ширину дерева и ширину ветвления O ( √ n ).
Для двух плоских графов с v вершинами можно определить за время O ( v ), изоморфны они или нет (см. Также проблему изоморфизма графов ).
Представимые в виде слов плоские графы включают в себя плоские графы без треугольников и, в более общем смысле, трехцветные плоские графы, а также определенные подразделения граней треугольных сеточных графов и определенные триангуляции покрытых сеткой цилиндрических графов.
Планарность
Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.
Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины это точки плоскости, а ребра линии на ней, области, на которые граф разбивает поверхность называются гранями. Плоский граф — граф уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.
Содержание
Критерий непланарности
Теорема Понтрягина-Куратовского
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.
Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.
Формула Эйлера
Для связного плоского графа справедливо следующее соотношение между количеством вершин V, ребер E и граней F:
Оно было найдено Эйлером в 1736 г. [1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум.
Формула имеет множество полезных следствий. Из того, что каждая грань ограничена не более чем тремя ребрами, следует, что для плоского графа
то есть, при большем числе ребер граф заведомо непланарен. (Обратное утверждение не верно, пример.) Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.
Планарные графы в задачах
Задача о трех колодцах. Есть три дома и три колодца. Доказать, что невозможно так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. (Мосты строить нельзя.)
Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны имеющий общий участок границы имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырех красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.
См. также
Примечания
Ссылки
Полезное
Смотреть что такое «Планарность» в других словарях:
Киприанов, Андрей Иванович — [р. 4 (16) июля 1896] сов. химик органик, акад. АН УССР (с 1945). В 1919 окончил Харьков. ун т, где работал до 1941 (с 1940 проф.). С 1944 проф. Киев. ун та; одновременно (с 1945) дир. Ин та органич. химии АН УССР. Осн. работы выполнены в области … Большая биографическая энциклопедия
ИНТЕГРАЛЬНАЯ СХЕМА — твердотельное устройство, содержащее группу приборов и их соединения (связи), выполненное на единой пластине (подложке). В И. с. интегрируются пассивные элементы (ёмкости, сопротивления) и активные элементы, действие к рых основано на разл. физ.… … Физическая энциклопедия
ГИПЕРГРАФ — обобщение понятия графа. Г. задается множеством V, элементы к рого наз. вершинами, и семейством подмножеств множества V, называемых ребрами Г.; Г. обозначается Понятие Г. является вариантом давно известных понятий комплекса, блок схемы, а также… … Математическая энциклопедия
Теория графов — Граф с шестью вершинами и семью рёбрами Теория графов раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строго … Википедия
Планарный граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия
Гамма-алгоритм — Гамма алгоритм алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация … Википедия
Гипотеза Хадвигера — Не следует путать с проблемой Нелсона Эрдеша Хадвигера. Гипотеза Хадвигера одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий k хроматический граф стягиваем к полному графу на вершинах.… … Википедия
Система графов — Системой графов является такая совокупность или множество графов, где между элементами зафиксировано соотношение. Графы систематизируются исходя из характеристик, чаще всего, таких как планарность, регулярность, транзитивность и т.д. Большая… … Википедия
Планарный график
СОДЕРЖАНИЕ
Теоремы Куратовского и Вагнера [ править ]
Вместо того, чтобы рассматривать подразделения, теорема Вагнера имеет дело с несовершеннолетними :
Минор графа результатов принимать подграф и неоднократно стягивание края в вершину, с каждым соседом исходных конечных вершин становится соседом новой вершины.
Другие критерии планарности [ править ]
На практике трудно использовать критерий Куратовского, чтобы быстро решить, является ли данный граф плоским. Однако существуют быстрые алгоритмы решения этой проблемы: для графа с n вершинами можно определить за время O ( n ) (линейное время), может ли граф быть плоским или нет (см. Проверка планарности ).
Для простого связного плоского графа с v вершинами, e ребрами и f гранями для v ≥ 3 выполняются следующие простые условия :
Формула Эйлера [ править ]
Средняя степень [ править ]
Графики монет [ править ]
Плотность планарного графика [ править ]
Связанные семейства графиков [ править ]
Максимальные планарные графики [ править ]
Внешнепланарные графики [ править ]
Графики Халина [ править ]
Другие родственные семейства [ править ]
Перечисление плоских графов [ править ]
Почти все плоские графы имеют экспоненциальное число автоморфизмов. [9]
Другие факты и определения [ править ]
Теорема о четырех цветах утверждает, что каждый плоский граф 4- раскрашиваем (т. Е. 4-долен).
Двойственные полезны, потому что многие свойства двойственного графа связаны простыми способами со свойствами исходного графа, что позволяет доказывать результаты о графах, исследуя их двойственные графы.
Хотя двойственный, построенный для конкретного вложения, уникален (с точностью до изоморфизма ), графы могут иметь разные (т. Е. Неизоморфные) двойственные, полученные из разных (т. Е. Негомеоморфных ) вложений.
Теорема о плоском разделителе утверждает, что любой планарный граф с n вершинами может быть разбит на два подграфа размером не более 2 n / 3 путем удаления O ( √ n ) вершин. Как следствие, планарные графы также имеют ширину дерева и ширину ветвления O ( √ n ).
Для двух плоских графов с v вершинами можно определить за время O ( v ), изоморфны они или нет (см. Также проблему изоморфизма графов ). [11]
Представимые в виде слов плоские графы включают плоские графы без треугольников и, в более общем смысле, трехцветные плоские графы, [13], а также некоторые подразделения граней треугольных сеточных графов [14] и некоторые триангуляции покрытых сеткой цилиндрических графов. [15]