АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Доказательство. Покажем, что K3,3 - это непланарный граф.

Покажем, что K _3,3 - это непланарный граф.

Предположим противное. Возьмем произвольную геометрическую реализацию этого графа на плоскости.

Рассмотрим последовательное прохождение вершин K ₃,₃ в следующем порядке: a - 2 - b - 3 - c - 1 - a. В рассматриваемом геометрическом представлении K ₃,₃ на плоскости этому прохождению соответствует перемещение по некоторой замкнутой линии, не имеющей самопересечений.

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

a 2

B

C 3

Рис. 5.7

Во внутренней и внешней областях должны быть изображены 3 ребра (которые обозначены на рисунке пунктирными линиями). Поэтому хотя бы в одной из этих областей необходимо провести не менее двух ребер. Нетрудно проверить, что во внутренней области невозможно провести более одного ребра так, чтобы соответствующие дуги не пересекались. Рассмотрим случай, когда во внутренней области изображается ребро (a, 3). Тогда ребра (b,1) и (c,1) должны изображаться дугами во внешней области. Но при любом изображении ребра (b,1) концы последнего ребра (c,1) невозможно соединить без пересечения уже проведенных линий. Это так поскольку всегда найдется такая замкнутая область на плоскости, образованная линиями, изображающими рёбра, что одна из вершин c и 1 содержится внутри, а другая снаружи этой области.

Поэтому предположение о существовании геометрической реализации графа K ₃,₃ является неверным.

Непланарность графа A ₅ доказывается аналогично приведенному доказательству непланарности графа K ₃,₃.

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

В определенном смысле графы K ₃,₃ и A ₅ являются каноническими непланарными графами. Оказывается, что все другие непланарные графы содержат в себе фрагменты, подобные либо графу K ₃,_3, либо графу A ₅.

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

Дата добавления: 2015-09-27 | Просмотры: 603 | Нарушение авторских прав