ГРАФ ПЛОСКИЙ это:

ГРАФ ПЛОСКИЙ

планарный граф,- граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии, соответствующие ребрам (исключая их концевые точки), не проходят через точки, соответствующие вершинам, и не пересекаются. К рассмотрению Г. п. сводятся такие задачи, как задача о раскраске карт, задачи о проектировании коммуникаций, задачи из радиоэлектроники, связанные с реализацией схемы с помощью плоских печатных подсхем, и др. Любая правильная (без пересечения ребер) укладка связного Г. п. порождает разбиение плоскости на отдельные области (грани). Такое разбиение плоскости наз. плоской картой. Для любой плоской карты имеет место формула Эйлера где n - число вершин, т - число ребер r - число областей карты (включая внешнюю область). Отсюда графы (полный граф с n=5) и (полный граф двудольный, имеющий по 3 вершины в каждой доле, см. рис. 1) не являются плоскими. Эти графы являются в нек-ром смысле минимальными неплоскими графами в силу теоремы Понтрягина - Куратовского: граф плоский тогда и только тогда, когда он не содержит подграфа, гомеоморфного графу пли (см. Графов гомеоморфизм).


Существуют п другие критерии планарности (т. е. свойства графа быть плоским). В частности, граф Gявляется плоским тогда и только тогда, когда каждая нетривиальная двусвязная компонента графа Gобладает таким базисом циклов и таким дополнительным циклом Z0, что любое ребро Gпринадлежит точно двум из этих m+1 циклов (базис циклов - это подмножество циклов данного графа, независимое и полное во множестве всех циклов графа относительно операции сложения по модулю 2, см. Граф).

Любой Г. п. можно изобразить на плоскости так, чтобы все его ребра являлись отрезками прямых. Любой трехсвязный Г. н. (см. Графа связность).единственным образом укладывается на сфере (с точностью до гомеоморфизма сферы). Каждой укладке Г. п. на плоскости, а следовательно и плоской карте, можно поставить в соответствие геометрически двойственный ей граф, получаемый следующим образом. В каждую область карты помещается но вершине Г. п., и если две области имеют общее ребро е, то помещенные в них вершины соединяются ребром е*, пересекающим только ребро е(на рис. 2 сплошными линиями изображена укладка Г. п., а штриховыми - двойственный ей граф). Плоская карта, каждая грань к-рой ограничена тремя ребрами, наз. плоской триангуляцией. Число ребер плоской триангуляции с пвершинами равно 3n - 6.

В теории графов большое внимание уделяется раскраскам Г. п. (см. Графа раскраска);для неплоских графов изучаются различные числовые характеристики, показывающие степень непланарности, напр, род, толщина, крупность графа, число скрещиваний и др. (см. Графа укладка).

Лит.:[1]Харари Ф., Теория графов, пер. с англ. М., 1973. В. Б. Алексеев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАФ ПЛОСКИЙ" в других словарях:

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

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

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

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

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

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

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

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

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

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


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

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