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

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

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

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

В качестве характеристики плоского графа вводят понятие грань.

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

Грани:

(2, 4, 5, 6, 2)

(1, 2, 3, 1)

(1, 7, 4, 1)

(1, 4, 2, 3, 1)

Границей грани называется простой цикл, ограничивающий грань.

Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

Существует так называемая бесконечная грань, т.е. часть плоскости, лежащая вне графа и ограниченная изнутри простым циклом

АВ называют перегородкой, и если у графа есть перегородка, то не существует бесконечной грани.

Теорема: Если в плоском представлении графа без перегородок V – количество вершин, P – количество ребер, G – количество граней (с учетом бесконечной), то V – P + G = 2 (формула Эйлера).

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