3 3 .Планарность графа, теорема Эйлера о многогранниках.

Граф наз. плоским, если его ребра не пересекаются.

Граф наз. планарным, если он изоморфен плоскому графу.

Граф G1 = (V1, E1) наз. изоморфным графу G2 = (V2, E2), если существует биекция f: V1→V2 такая, что для любых вершин х, уєV1 число ребер из Е1, инцидентных этим вершинам, равно числу ребер из Е2, инцидентных вершинам f(x) и f(у).

Ex: Графы G1 и G2 изоморфны.

Плоские графы

Ех: Планарные графы

Ех: Не планарные графы

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

Теорема: Граф укладывается на сфере тогда и только тогда, когда он планарен.

Д ок-во: Предположим, что граф G уложен на сфере S. Выберем на сфере точку N, которая не лежит ни на одном ребре графа и не совпадает с вершиной. В точке сферы, противоположной точке N, проведем касательную плоскость π. Из точки N спроектируем сферу S без точки N на плоскость π. Обозначим образ графа G через G′. Т.к. проекция явл. биекцией сферы S|{N} на плоскость π, граф G′ явл. плоским и изоморфным исходному графу G -» G - планарный граф.

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

Р1 = {a1,a3,a2,a4} и соединяющие их ребра.

Р2 = {a3, a4, a5, a6} и соединяющие их ребра.

Теорема:Для любого связного графа число вершин n, число ребер m, число граней r связаны соотношением: n – m + r = 2 (*)

Док-во: Пусть G – связный плоский граф, т.е. состоящий из одной компоненты связности. Предположим, что G не имеет циклов, значит G явл. деревом, т.е. обыкновенным связным граф без циклов.) => n = m + 1 и r = 1 => n – m + r = m+1-m+1 = 2.

Предположим, что граф G содержит циклы. Рассмотрим ребро е, принадлежащее циклу => ребро е не явл. мостом и принадлежит двум граням р1 и р2, одну из которых можно считать внешней. Рассмотрим граф G′ = G – е. Граф G′ - связный и плоский (по теореме: если в связном графе удалить ребро, принадлежащее циклу, то граф останется связным). При удалении ребра е грани р1 и р2 сольются в одну внешнюю грань графа G′. Остальные грани останутся без изменения => граф G′ содержит на одно ребро и одну грань меньше, чем граф G. Т.к. число вершин этих графов совпадает, то выполняется равенство:

n ′ - m′ + r′ = n – m + r => при удалении ребра левая часть рав-ва (*) не меняется. Но разрывая циклы, получаем дерево, для которого (ранее доказано) выполняется рав-во (*) => для исходного графа рав-во (*) верно.

Следствие 1: Для плоского графа, имеющего С компонент связности, выполняется рав-во: n – m + r = 1 + c

Следствие 2: Граф К5 не планарен.

Следствие 3: Граф К3,3 не планарен.