Плоские графы.
Граф - плоский, если его можно нарисовать на плоскости так, чтобы два его ребра не имеют других общих точек, кроме их общей вершины.
Рисунок графа, в котором ни какие его два ребра не пересекаются, называется плоским представлением графа.
Пример плоского графа: простые циклы, деревья, лес.
В качестве характеристики плоского представления графа вводится понятие грани.
Гранью называется часть плоскости, ограниченная циклом и не содержащая внутри
других циклов.
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