1.4. Изоморфизмы и реализации

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

Ранее было отмечено, что любой граф в абстрактном смысле идентичен, или, используя более принятый термин, изоморфен некоторому геометрическому графу. Изоморфизм графов формально определяется следующим образом: говорят, что графы изоморфны друг другу, если существует взаимно однозначное соотношение между и между сохраняющее отношения инцидентности. Иначе говоря, ребро инцидентно вершине графа тогда и только тогда, когда инцидентны соответствующие элементы в графе Если граф изоморфен геометрическому графу С, тогда называется геометрической реализацией графа (В частности, геометрический граф можно рассматривать как геометрическую реализацию самого себя.)

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

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

существенные отличия с точки зрения топологии, с точки зрения теории графов они эквивалентны.

Рис. 1.2.

На рис. 1.3 показан неплоский граф, т. е. граф, не имеющий геометрической реализации в пространстве Граф иллюстрирует одну из двух фундаментальных конфигураций, которые характеризуют все неплоские конечные графы. Этот результат, следующий из важной теоремы, принадлежащей Куратовскому, устанавливается в главе 4, где исследуются особенности плоских графов. Если в пространстве только ограниченный класс конечных графов имеет геометрическую реализацию, то для пространства справедливо следующее утверждение.

Рис. 1.3.

Теорема 1.1. Любой конечный граф имеет геометрическую реализацию в

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

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

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

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

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

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

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

доказательства теоремы 1.1) выбрать различные точки на для каждой вершины и различные полуплоскости для каждой неупорядоченной пары вершин. Как только это сделано, в плоскости можно построить кривые согласно схеме, показанной на рис. 1.4.

Рис. 1.4.

Каждая точка на отрезке определяет простую кривую (ломаную линию или круг), которая не совпадает с другими такими же кривыми, за исключением точек