Граф, который можно изобразить на плоскости без пересечения ребер вне вершин, называется плоским топологическим графом

Определение графа

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

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

ПЛОСКИЕ ГРАФЫ

Граф, который можно изобразить на плоскости без пересечения ребер вне вершин, называется плоским топологическим графом.

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

Формула Эйлера. Если связный плоский топологический граф имеет n вершин, m ребер и f граней, то n-m+f=2.

Пример. Примером неплоского графа может служить полный граф с пятью вершинами. Любые попытки начертить его плоское представление обернутся неудачей.

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

Пример.

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