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

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

• Определение №2: ( Планарный граф )
Графы, изоморфные плоским графам называются планарными.

*** Плоская укладка ***

• Определение №3: ( Укладка графа G в пр-во L )
Если для графа G сущ. соответствие каждой в-не некоторой точки в пр-ве L и каждого ребра Жардановой кривой (спрямляемая кривая без самопересечений), такое что любые 2 Жардановые прямые, соединяющие соответствующие в-ны, пересекаются лишь в инцидентных им в-нам, то говорят, что граф G укладывается в пр-во L (имеет укладку в пр-во L)

*** Теоремы об укладке графа на пл-ти и на сфере ***

• Теорема №1:
Любой граф имеет укладку в 3-ех мерное пр-во.

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

• Теорема №2:
Граф планарен <=> когда имеет укладку на сфере.

-> Док-во:
Пусть граф имеет укладку на сфере.
Покажем, что он планарен.
Проведем пл-ть, касательную к сфере так, чтобы точка сферы, противоположная точки касания с пл-тью (северный полюс N) не находилась бы ни на одном ребре графа.
Строим стереоскопическую проекцию графа G на пл-ть Q, проводя прямые через N и все точки графа G, расположенного на сфере, до пересечения с пл-тью Q/
Точки пересечения явл-ся стереоскопическими проекциями соответствующих точек графа G.
Т.к. стереоскопическая проекция обеспечивает биективное отображение всех точек сферы кроме N на пл-ти Q, то граф, являющийся проекцией гр. G на пл-ть Q соответствует следующему условию:
любые 2 его ребра пересекаются лишь в инцидентных им в-нах, т.е. полученный граф является плоским и изоморфным графу G
=> граф G явл. планарным.