Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Геометрические реализации абстрактных графов

Пусть G(V, Е) - абстрактный граф. Геометрической реализацией графа G(V, Е) называется любой геометрический граф G'(V' Е'), изоморфный графу G(V, Е).

Если абстрактный граф можно реализовать в виде плоского геометрического графа, то он называется плоским графом. Далеко не всякий граф (даже конечный!) можно реализовать в виде плоского геометрического графа. Заметим, что на плоскости можно изобразить любой конечный граф, но при этом в большинстве случаев изображение будет «неправильным», т.е. не будет выполняться условие 3 из определения геометрического графа (некоторые ребра будут иметь пересечения в точках, не являющихся вершинами графа). Оказывается, что для геометрической реализации любого конечного графа, или графа со счетными множествами вершин и ребер, вполне достаточно трехмерного пространства. Более того, справедлива следующая теорема.

Теорема 2. В трехмерном пространстве реализуются все те графы, множества вершин и ребер которых находятся во взаимно-однозначных соответствиях с некоторыми подмножествами множества действительных чисел[1].

Доказательство. Пусть задан абстрактный граф G(V, Е), удовлетворяющий условию теоремы.

1. Зафиксируем в пространстве некоторую прямую /. Каждой вершине jc графа G(V, Е) поставим в соответствие определенную точку х' на прямой /. По условию теоремы точки, соответствующие вершинам графа G(V, Е), можно выбрать на прямой I так, чтобы различным вершинам соответствовали различные точки (см. пример на рис. 13).

Рис. 13

2. Каждому ребру е графа G(V, Е) поставим в соответствие определенную полуплоскость Н(е) пространства с границей I так, чтобы различным ребрам соответствовали различные полуплоскости. Это возможно по условию теоремы (см. пример на рис. 14).

3. Для каждого ребра е в полуплоскости Н(е) выберем простую кривую е' в виде полуокружности или окружности (для петли), соединяющую точки, соответствующие граничным вершинам ребра е (см. пример на рис. 15). Обозначим через V’ множество полученных точек, а через Е’~ множество полученных простых кривых. Тогда пространственный геометрический граф G’(V Е') будет изоморфен абстрактному графу G(V, Е).

Рис. 15

Следствие. Любой конечный граф или граф со счетным числом элементов имеет геометрическую реализацию в трехмерном пространстве.

Далее мы будем рассматривать лишь графы с не более чем счетным числом элементов. Поэтому, в силу теоремы 2, эти графы всегда можно мыслить как пространственные геометрические графы.

Граф называется элементарным, если он не содержит петель и параллельных ребер.

Теорема 3. Любой элементарный конечный граф реализуется в виде пространственного геометрического графа, ребра которого являются прямолинейными отрезками.

Действительно, пусть элементарный конечный граф G(V, Е) имеет п вершин и т ребер (|v| = п, |е| = т). Так как каждая пара вершин такого графа инцидентна не более

чем одному ребру, то т<С* = ^-П-. Поставим в

соответствие каждой вершине графа G(V, Е) точку евклидова пространства так, чтобы все полученные и точек находились в общем положении (никакие 4 из них не лежали в одной плоскости). Тогда любые две прямые, соединяющие пары из четырех различных точек, являются скрещивающимися и не имеют общих точек. Каждому ребру графа G(V, Е) поставим в соответствие отрезок прямой, соединяющий соответственные точки пространства. Ясно, что граф, состоящий из п выбранных точек и т выбранных отрезков, является искомой геометрической реализацией графа G(V, Е).

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

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

На рис. 16 представлены геометрические

реализации полных графов с п вершинами при п = 1, 2, 3, 4, 5. Ребра этих графов представлены прямолинейными отрезками.

Замечание. Каждый абстрактный граф имеет бесконечное множество геометрических реализаций. Так, при топологическом преобразовании' (гомеоморфизме) геометрического графа всегда получается граф,

Рис. 16

изоморфный данному. Два изоморфных геометрических графа всегда гомеоморфны. Частным случаем топологического преобразования графов является их непрерывная деформация. Если представить, что граф состоит из резиновых нитей (вместо ребер) и узелков (вместо вершин), то всевозможные пластические изменения формы такого графа будут являться его непрерывными деформациями. Не всякие изоморфные графы могут быть переведены один в другой при помощи непрерывной деформации. Так, например, пространственные графы G/ и G2 на рис. 17 изоморфны, но не существует непрерывной деформации, переводящей один из этих графов в другой. Если рассматривать графы G/ и Сг как геометрические графы в четырехмерном пространстве, то там можно будет подобрать непрерывную деформацию, переводящую эти графы один в другой.

' Топологическое преобразование - это взаимно однозначное и взаимно непрерывное отображение. Это самое общее из возможных геометрических преобразований, сохраняющих размерность.

Рис. 17

  • [1] Граф G(V, Е) имеет геометрическую реализацию в трехмерномпространстве тогда и только тогда, когда кардинальные числамножеств V и Е не превосходят континуума, т.е. кардинальногочисла множества всех действительных чисел.
 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы