13. Необходимые условия планарности, формула Эйлера для планарных графов.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Всякий граф можно изобразить на плоскости в виде точек и непрерывных линий, соединяющих эти точки. При этом один и тот же граф может иметь бесконечно много различных изображений (укладок графа на плоскости).

Определение. Изображение графа на плоскости без внутренних точек пересечения ребер называется плоской укладкой графа.

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

Утверждение 1 (необходимое условие планарности). Для любого связного планарного графа с n вершинами и m ребрами, где n ≥ 3, выполняется неравенство .

Утверждение 2 (необходимое условие планарности). В любом планарном графе есть вершина, степень которой не превосходит пяти.

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

Формула Эйлера. Для всякого планарного графа справедлива формула Эйлера: , гдеn– количество вершин,g– граней,m– ребер,k– компонент связности в исходном графе. Под гранями здесь понимаются связные области, на которые распадается плоскость, если провести «разрезы» по всем ребрам плоской укладки графа. Для связного планарного графа формулу Эйлера можно записать иначе:.