Определение

Графы G₁= (V₁, U₁) и G₂ = (V₂, U₂) называются изоморфными, если существует такое биективное отображение h: V₁  V₂, для которого ((a, b) U₁  (h(a), h(b)) U₂).

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

a 1

b 2

c 3

d 4

e 5

f 6

g 7

h 8

Для доказательства изоморфизма произвольных двух графов G₁ и G₂ на основе определения изоморфизма необходимо построить подходящее биективное отображение. Простейший способ поиска такого отображения состоит в последовательном построении всех возможных биективных отображений множества вершин одного графа на множество вершин другого графа. Для каждого такого отображения проверяется выполнение условий изоморфизма.

При этом графы являются неизоморфными, если ни одно проверяемое отображение не устанавливает изоморфизм между G₁ и G₂.

Из определения изоморфизма следует, что изоморфные графы имеют общие свойства, в которых не используется именование вершин. Например, если графы G₁ и G₂ изоморфные и h – подходящая биекция вершин этих графов, то ребра (a, b) и (h(a),h(b)) одновременно являются ориентированными или неориентированными.

Аналогично, если в одном графе имеется вершина степени 5, то и в другом графе должна иметься вершина с таким же свойством.

Поэтому неизоморфны графы, изображенные на рис.5.5:

G ₁ G₂

Рис. 5.5

Действительно, в G₂ имеется вершина степени 4, а в G₁ нет вершин, с таким свойством.

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

5.4. Планарность графов

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

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

ТЕОРЕМА 5.1

Всякий граф имеет геометрическую реализацию в трехмерном пространстве.

Доказательство

Пусть G = (V, U), где V = {v₁, ... v_n} и U = {u₁, ... , u_k}.

Возьмем в трехмерном пространстве n точек, последовательно расположенных на некоторой прямой l. Припишем этим точкам имена вершин графа.

Через прямую l проведем k плоскостей P₁, . . . , P_k, пересекающихся по этой прямой. Например, это можно сделать, если провести плоскость P₁, а затем получать новые плоскости, последовательно поворачивая P₁ на угол, кратный 180⁰/k в одном и том же направлении.

Изобразим ребра графа G так, чтобы дуга, представляющая ребро u_i, проводилось в плоскости P_i и пересекала l только в конечных точках.

Построенное в результате представление графа G является его геометрическим заданием.

Доказательство окончено.