Укладки графов. Планарные графы

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

Пример. Полный граф (граф, содержащий всевозможные ребра) на и вершинах является планарным ():

Примеры непланарных графов:

полный граф на вершинах () является непланарным;

двудольный граф с вершинами в каждой доле () является непланарным.

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

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

Покажем непланарность графов и .

Предположим противное: граф планарен. Рассмотрим укладку этого графа на плоскости без пересечений ребер. Рассмотрим цикл из ребер, который соединяет рассмотренные вершины. Этот цикл разобьет плоскость на две связные области и (любую пару вершин из одной и той же области можно соединить непрерывной линией, которая не пересекает ребра цикла, а пару вершин из различных областей связности соединить непрерывной линией без пересечений ребер нельзя). Рассмотрим ребро укладки, которое соединяет пару вершин и .

Это ребро будет расположено либо в области , либо в области . Эти возможности подобны. Предположим, это ребро расположено в области . Тогда пара вершин , должна быть соединена ребром, расположенном в области . Другая пара вершин – , должна быть соединена ребром, расположенном в области . Пара вершин , должна соединяться ребром из области . Тогда пару вершин , нельзя соединить ребром, не пересекающим другие ребра укладки.

Покажем непланарность графа .

Такой граф содержит цикл, состоящий из ребер. Доказательство будем строить от противного. Предположим, что существует планарная укладка графа на плоскости. Тогда цикл из ребер разбивает плоскость на две области связности: и . Вершины и должны соединяться ребром, которое проходит либо в , либо в . Эти возможности рассматриваются подобным образом. Пусть ребро проходит в , тогда вершины , должны соединяться ребром в . Тогда вершины и соединить без пересечения других ребер нельзя.

Таким образом, показано, что графы и непланарны.

Что и требовалось доказать.

Определение. Рассмотрим укладку планарного графа на плоскости. Тогда ребра графа разрезают плоскость на связные области, которые будем называть гранями укладки.

Дата добавления: 2017-01-13