Рассмотрим в трёхмерном пространстве или на плоскости геометрические фигуры, состоящие из точек-вершин и кривых-дуг, каждая из которых соединяет некоторые пары вершин. Эти кривые не имеют общих точек, кроме вершин. Фигура Г называется геометрической реализацией графа G, если Г» G. Фигура Г на плоскости называется плоским графом.
ТЕОРЕМА. Каждый конечный граф имеет геометрическую реализацию в трёхмерном пространстве.
Доказательство. Пусть граф G содержит n вершин и h рёбер. Проведём через произвольную прямую h плоскостей. На прямой выберем n точек, которые сопоставим вершинам графа. Каждому ребру графа G сопоставим плоскость из данного пучка плоскостей и в ней проведём соответствующую дугу. ■
Граф называется планарным, если существует его геометрическая реализация на плоскости. Введём операцию подразбиения ребра графа G. Пусть – произвольное ребро графа, . Операция подразбиения ребра заключается в построении нового графа с множеством вершин и множеством рёбер .
Граф G 2называется подразбиением графа G 1, если он может быть получен из G 1путём применения конечного числа раз операции подразбиения рёбер. Графы G 1и G 2называются гомеоморфными, если существуют их изоморфные подразбиения.
|
|
Любой планарный граф допускает реализацию в виде плоского графа, у которого все рёбра – отрезки прямых. Часть плоскости, которая ограничена рёбрами плоского графа и не содержит других рёбер, кроме граничных, называется гранью. Для каждого плоского графа имеется внешняя грань.