31. Планарные графы.

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

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

Если граф имеет подграф K5 (К5 не имеет планарной укладки), то он не планарный.

Операцией подразбиение ребра в графе называется замена некоторого ребра (i,j) парой рёбер (i,k) и (k,j), причём вершина k не входило в исходное множ вершин графа.

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

Теорема Куратовского Понтрягина. Граф является планарным тогда и только тогда, когда, когда он гомеоморфный графу, не содержащий подграфов K5 и K3,3. Для распознования планарных графов можно воспользоваться следующей процедурой:

1.В каждой компоненте связности последовательно по ребру стянуть все такие пары вершин, одна из которых исеет степень 2;

2.Перебрать всевозможные подграфы с 5, 6 вершинами

Если каждый такой подграф отличен от К5 и К3,3, то исходный граф- планарный, иначе граф не планарный.