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

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

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

Пример плоского графа: простые циклы, деревья, лес.

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

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

других циклов.

 

2 3 (1 2 3 4 – грани) 1 2 4 1 – не грань

7 4 5 1 3 2 1

5 1 3 2 4 1 - грани

3 2 6 5 4 2

1 4

1 2 6

Мост, соединяющий два цикла, называется перегородкой. Простой цикл, ограничивающий грань называется границей грани. Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

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

Эту часть плоскости называют бесконечной гранью.

 

Бесконечная не

грань бесконечная

 

 

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

Для любого плоского представления связного графа без перегородок число вершин v, число ребер r и число граней g связаны соотношения

v- r + g = 2