Лекции по "Развитию операционных систем"

,

 

 

11.2.  Критерии планарности графа.

 

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

 

Теорема 11.2.  Полный двудольный граф K3,3 не является планарным.

Доказательство.

Используем метод «от противного» и предположим, что граф K3,3 – планарный.

Если K3,3 планарный граф, и поскольку имеется девять ребер и шесть вершин, то . Поэтому .

Пусть A и B – непересекающиеся трехэлементные множества вершин, формирующие множество V вершин графа K3,3. Если начать путь из одного из непересекающихся множеств, например, A, и не повторять ребра, то можно попасть в вершину из множества B, вернуться в вершину из множества A, вернуться в вершину из множества B и, наконец, вернуться в вершину множества A, прежде чем завершить цикл. Каждый цикл в K3,3 представляет собой путь, длина которого, по крайней мере, равна 4. Поэтому каждая грань определена циклом, в котором не менее четырех ребер. Следовательно, сумма ребер всех граней больше, чем . Но каждое ребро подсчитывается не более двух раз, поскольку оно может служить границей только двух граней. Значит, сумма ребер граней должна быть меньше, чем . Объединяя эти неравенства, получаем, . Поэтому . Но это противоречит тому, что .

Следовательно, мы пришли к противоречию, и граф K3,3 не является планарным.

■

Следующую лемму примем без доказательства.

 

Лемма 11.3.  В произвольном связном планарном графе G с количеством вершин не менее трех имеет место неравенство .

 

Теорема 11.4.  Полный граф K5 не является планарным.

Доказательство.

Граф K5 имеет пять вершин и десять ребер, .Поэтому, согласно лемме 11.3., граф K5 не является планарным.

■

 

Если граф G(V, E) содержит ребро e=(vi, vj) и граф G¢(V¢, E¢) получен из графа G(V,E) добавлением новой вершины v в множество V и заменой ребра (vi, vj) ребрами и , то граф G¢(V¢, E¢) называется расширением графа G(V, E). Если графы таковы, что является расширением графа , то граф называется производным от графа .

Если граф G¢(V¢, E¢) – расширение графа G(V, E), то посередине одного из ребер появляется вершина, а исходное ребро делится на два новых ребра, которые соединяют вершины, инцидентные исходному ребру, и новую вершину.

 

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

 

Пример 11.4.  Граф, который изображен слева, является расширением графа, изображенного справа.

 

,

Пример 11.5.  Граф, который изображен слева, является производным от графа, изображенного справа.

 

,

Рассмотрим следующие критерии планарности графа в качестве теорем без доказательства.

 

Теорема 11.5.  Каждый планарный граф содержит вершину степени 5 или менее.

 

Теорема 11.6.  Если два связных графа гомеоморфные, то они либо оба планарные, либо оба не планарные.

 

Теорема 11.7.  (теорема Понтрягина – Куратовского)

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