1.2. Геометрические графы

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

Обозначим -мерное евклидово пространство через (Далее при обсуждении результатов теорем 1.1 и 1.2 нас будут интересовать в основном двух- и трехмерные пространства.)

Евклидово -мерное пространство есть множество последовательностей из действительных чисел в котором расстояние между любыми двумя точками определено следующим образом:

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

Аналогично, простой замкнутой кривой называется непрерывная самонепересекающаяся кривая, конечные точки которой совпадают.

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

1. Каждая замкнутая кривая в содержит только одну точку множества

2. Каждая незамкнутая кривая в содержит ровно две точки множества У, которые являются ее граничными точками.

3. Кривые в не имеют общих точек, за исключением точек из множества

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

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

Обычная форма представления геометрического графа показана на рис. 1.1. С позиций теории графов элементы называются геометрическими вершинами и геометрическими ребрами соответственно.

Рис. 1.1

Введем теперь различные описательные термины, которые составляют основной словарь теории графов. (Например, ребра на рис. 1.1 называются параллельными, вершина и

называется изолированной, вершины называются смежными и т. д.).

Предварительно дадим определение графа в более общем виде.