Инструменты пользователя

Инструменты сайта


examination:diskretka:question8

Вопрос №8. Плоские (планарные) графы. Минимальные неплоские графы. Критерий Понтрягина-Куратовского планарности графа.

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

Иначе говоря, любые 2 отрезка, изображающие ребра графа, могут пересекаться только в своих концах. Замечания:

  1. свойство графа быть плоским называется планарностью
  2. в определении плоского графа наличие или отсутствие ориентации ребер не имеет никакого значения; таким образом, понятие планарности естественно связывать с неорграфами, а если граф не такой, то следует забыть об ориентации тех его ребер, которые были ориентированными
  3. наличие петель никак не влияет на свойство планарности (если их не слишком много, то есть ели мощность множества петель не превосходит мощности континуума); это означает, что в исследовании графа на планарность о петлях можно забыть
  4. на планарность не влияет наличие кратных ребер (если их не слишком много), так как семейство параллельных ребер с одинаковым началом и концом можно свернуть в жгут и рассматривать потом как 1 ребро
  5. аналогичную задачу можно представить в пространствах более высокой размерности: ввести понятие объемный граф – граф, имеющий геометрическую модель без внутренних пересечений ребер, расположенную в трехмерном пространстве. Всякий граф, у которого мощности множеств ребер и вершин не превосходят мощности континуума, имеет указанную геометрическую реализацию. Значит, такое обобщение планарности на многомерное пространство бессодержательно.
  6. планарность – одно из немногих свойств графа, являющееся чисто геометрическим. Это означает, что стандартные комбинаторные алгоритмы исследования графа на планарность являются неочевидными. Как ни странно, имеется способ проверки графа на планарность, имеющий комбинаторную природу. Это теорема Понтрягина-Куратовского.

Утверждение: всякая часть плоского графа самая является плоским графом

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

Замечание: всякий неплоский граф содержит часть, являющуюся минимальным неплоским графом.

Замечание: неплоский граф может содержать своей частью несколько минимальных неплоских графов.

Теорема Понтрягина-Куратовского: с точностью до изоморфизма существует ровно 2 различных минимальных неплоских графа:

Следствие из теоремы (критерий Понтрягина-Куратовского) : граф является плоским, если он не имеет части, изоморфной какому-либо из 2 минимальных неплоских графов.

examination/diskretka/question8.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)