3.2. Изоморфизм. Плоские графы. Реализуемость в r

Похожесть и непохожесть однотипных объектов в математике определяется понятием изоморфизм.

Изоморфные графы (орграфы) имеют одинаковое число вершин и дуг и отличаюся лишь их обозначением, т.е. если можно переименовать вершины и дуги графа (орграфа) G так, чтобы получился граф G₁, то графы G и G₁ будут изоморфными.

На рис.3.5 изображены два изоморфных графа. Это следует из того, что вершины и дуги графа G₂ можно переименовать так:

2 → 1, 1 → 3, 3 → 2; x₁ → x₃, x₃ → x₁, x → x .

У изоморфных графрв степени соответствующих друг другу вершин должны совпадать.

Рис. 3.5

На рис.3.6 изображены три орграфа. Орграф G₁ изоморфен орграфу G₂. Это следует из того, что вершины и дуги орграфа G₂ можно переименовать следующим образом:

1 → 4, 2 → 3, 3 → 1, 4 → 2;

x → x , x → x , x → x , x → x , x → x , x → x .

В результате этого переименования из орграфа G₂ получится следующий орграф

Сравнивая полученный граф с графом G рис.3.6, видим, что они совпадают. Такое переименование удалось сделать потому, что вершины этих орграфов “похожи”, т.е. двум вершинам каждого орграфа инцидентны две заходящие дуги и одна выходящая, а двум остальным вершинам инцидентны одна заходящая и две выходящих дуги.

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

Орграф G₃ не изоморфен орграфу G₁, т.к. вершине 3 орграфа G₃ инцидентны три заходящие дуги. Аналогичной вершины нет в орграфе G₁. Следовательно, эти орграфы не изоморфны.

Рис. 3.6

Для определения изоморфизма между орграфами G и G можно предложить следующий алгоритм.

Шаг 1. Если число вершин и число дуг, соответственно, совпадают для орграфов, то переходим к шагу 2. Иначе орграфы не изоморфны.

Шаг 2. Для каждой вершины орграфов определяем пары чисел, равные полустепе-ням захода и исхода. Если каждой такой паре орграфа G найдется аналогичная пара орграфа G , то переходим к шагу 3. Иначе орграфы не изоморфны.

Шаг 3. Если каждой рассмотренной паре чисел для орграфа G соответствует единственная аналогичная пара орграфа G , то есть единственное соответствие между вершинами орграфов из которого можно легко установить соответствие между дугами орграфов, т.е. они будут изоморфными.

Если некоторой паре орграфа G соответствует не одна аналогичная пара орграфа G , то этой вершине орграфа G ставим в соответствие поочередно вершины орграфа G с аналогичной парой чисел.

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

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

По подстановкам дуг, вошедшим в полную подстановку дуг, получим подстановку для вершин орграфов.

Рассмотрим работу предложенного алгоритма для установления изоморфизма между орграфами G и G рис.3.6.

Шаг 1. У каждого из рассматриваемых орграфов по 4 вершины и по 6 дуг. Переходим к шагу 2.

Шаг 2. Для каждой вершины орграфов определяем пары чисел – полустепени захода и исхода ( deg v , deg v ). Эти пары представлены в следующей таблице

орграф	v	v	v	v
G	(1,2)	(2,1)	(1,2)	(2,1)
G	(1,2)	(2,1)	(2,1)	(1,2)

Из этой таблицы видно, что каждой паре орграфа G можно найти аналогичную пару орграфа G . Переходим к шагу 3.

Шаг 2. Вершине v орграфа G соответствует пара (1,2). У орграфа G таких пар две. Следовательно, этой вершине можно сопоставить вершины v и v орграфа G

Вначале поставим этой вершине в соответствие вершину v орграфа G . Тогда по инцидентным этим вершинам дугам составим следующие подстановки

п₁ = и п₂ = .

В этих и в последующих подстановках дуги в верхней строке относятся к орграфу G , а дуги нижней строки относятся к орграфу G .

Далее вершине v орграфа G поставим в соответствие вершину v орграфа G . Тогда получим следующие подстановки для дуг

п₃ = и п₄ = .

Из таблицы видно, что вершине v орграфа G можно сопоставить вершины v и v . Из сопоставления v → v получим подстановки

п₅ = и п₆ = .

Из сопоставления v → v получим подстановки

п₇ = и п₈ = .

Вершине v орграфа G можно сопоставить вершины v и v орграфа G .

Из сопоставления v → v получим подстановки

п₉ = и п₁₀ = .

Из сопоставления v → v получим подстановки

п₁₁ = и п₁₂ = .

Вершине v орграфа G можно сопоставить вершины v и v орграфа G .

Из сопоставления v → v получим подстановки

п₁₃ = и п₁₄ = .

Из сопоставления v → v получим подстановки

п₁₅ = и п₁₆ = .

При изоморфизме орграфов, если вершина v орграфа G соответствует вершине v орграфа G , то подстановка дуг, полученная из этого соответствия, не должна проти-воречить ( n-1 ) подстановкам, полученных из-за соответствия для остальных (n-1 ) вершин орграфа G .

Для нашего примера такая подстановка должна не противоречить трем подста-

новкам, иначе вершина v орграфа G не будет соответствовать вершине v орграфа G .

Рассмотрим подстановки п₁ и п₂. Каждая из них не противоречит только одной из приведенных выше, соответственно подстановкам п₅ и п₁₄. Следовательно, вершина v орграфа G не соответствует вершине v орграфа G .

Следующая подстановка п3 не противоречит трем подстановкам п₈, п₉ и п₁₃. Из этого следует подстановка для вершин

Пв = ,

где первая строка это вершины орграфа G , а вторая строка вершины орграфа G .

Объединяя указанные подстановки получим полную подстановку для дуг орграфов

Пд = .

Из полученных подстановок Пв и Пд следует, что орграфы изоморфны.

Представленное ранее переименование вершин и дуг орграфа G полностью соответствует этим подстановкам.

Определение. Подразбиением (измельчением) дуги v_i в неориентированном графе или в орграфе называется замена ее на две новые и добавление одной новой вершины. На рис.3.7 показано подразбиение дуги графа и дуги орграфа.

Рис. 3.7

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

Гомеоморфными графами (орграфами) называются графы (орграфы) для которых существует их подразбиения, являющиеся изоморфными графами. На рис.3.8 показаны два гомеоморфных графа G₁ и G₂. Крестиками показаны дуги графов, которые должны подвергнуться подразбиению, чтобы графы стали изоморфны.

G G

Рис. 3.8

Определение. Геометрическим графом называется граф у которого множество вершин – множество отмеченных точек в R₂ или в R₃, множество дуг – множество параметризованных отрезков непрерывных кривых в R₂ или в R₃, концами которых являются соответствующие им вершины.

Теорема. Для любого графа существует изоморфный ему геометрический граф (в R₂ или в R₃) называемый геометрической реализацией.

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

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

Графы на рис.3.6 не являются правильно реализованными, а графы на рис.3.8 - правильные.

Теорема. Для любого графа существует его правильная реализация в R₃.

Доказательство: Возьмем в R₃ произвольную прямую s. Вершинам графа поставим в соответствие отмеченные точки на этой прямой. Каждой дуге графа будет соответствовать своя плоскость, проходящая через s. В этой плоскости проводится эта дуга или петля. Очевидно, что эта конструкция дает правильную реализацию графа.

Определение. Граф называется плоским (планарным), если у него существует правильная реализация в R₂.

Граф G₄ рис.3.9 является плоским, поскольку у него есть правильная реализация на плоскости, т.е. он может быть изображен в виде графа G₆ рис.3.9. Граф G₅ рис.3.9. не является планарным.

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

Н а рис.3.9 представлены полные графы.

Рис.3.9

Определение. Полным двудольным графом G (n ≤ m) называется граф с n + m вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого множество вершин разбито на два непересекающихся подмножества с n и m вершинами, так что любые две вершины различных подмножеств соединены дугой и никакие две вершины одного подмножества не соединены дугой.

На рис.3.10 показаны двудольные графы.

Рис.3.10

Оказывается, что граф G₅ на рис.3.9, граф G_3,3 на рис.3.10 и графы, части которых устроены “подобно“ им, не являются плоскими. Значение этого факта и теоремы о правильной реализуемости графов в R₃ для микроэлектроники трудно переоценить. Фактически из-за этих графов пришлось создавать технологию многослойных печатных плат или микросхемы в виде сэндвичей.

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

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

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