Формула Эйлера

Теорема (Понтрягин-Куратовский)

Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы К₅ и К_3,3 (быть может с добавочными вершинами степени 2).

(ВИКИПЕДИЯ – простейшие свойства)

Формула Эйлера

Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань):

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

следовательно,

то есть, при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение не верно: в качестве контрпримера можно взять граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Общая формула также легко обобщается на случай несвязного графа:

где — количество компонент связности в графе.

12. Степени вершин графа, теорема о сумме степеней и следствие из неё. (википедия)

Степень вершины (валентность) — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды. Степень вершины обозначается как (в западных источниках — ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Поиск по сайту: