Геометрическая реализация графа

Рассмотрим в трёхмерном пространстве или на плоскости геометрические фигуры, состоящие из точек-вершин и кривых-дуг, каждая из которых соединяет некоторые пары вершин. Эти кривые не имеют общих точек, кроме вершин. Фигура Г называется геометрической реализацией графа G, если Г» G. Фигура Г на плоскости называется плоским графом.

ТЕОРЕМА. Каждый конечный граф имеет геометрическую реализацию в трёхмерном пространстве.

Доказательство. Пусть граф G содержит n вершин и h рёбер. Проведём через произвольную прямую h плоскостей. На прямой выберем n точек, которые сопоставим вершинам графа. Каждому ребру графа G сопоставим плоскость из данного пучка плоскостей и в ней проведём соответствующую дугу. ■

Граф называется планарным, если существует его геометрическая реализация на плоскости. Введём операцию подразбиения ребра графа G. Пусть – произвольное ребро графа, . Операция подразбиения ребра заключается в построении нового графа с множеством вершин и множеством рёбер .

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

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