Изоморфизм и гомеоморфизм графов

Определение Функция f: G (V, E) ® G ₁ (V ₁, E ₁ ) является изоморфизмом (обозначается G ~ G ₁), если f: V ® V ₁ и f: E ® E ₁ представляют собой взаимно однозначные соответствия. Если f: G ® G ₁ – изоморфизм, то G и G ₁ называются изоморфными.

Пример Дан неориентированный помеченный граф G ₁(V ₁; E ₁). Построить изоморфные ему графы.

,

Теорема. Изоморфизм графов есть отношение эквивалентности.

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

[ Рефлексивность. ] G ~ G, где требуемая биекция есть тождественная функция;

[ Симметричность. ] Если G ₁ ~ G ₂ с биекцией h, то G ₂ ~ G ₁ с биекцией h ^{- 1};

[ Транзитивность. ] Если G ₁ ~ G ₂ с биекцией h и G ₂ ~ G ₃ с биекцией g, то G ₁ ~ G ₃ с биекцией g o h.

Говорят, что сети G ₁ = {N ₁, A ₁ } и G ₂ = {N ₂, A ₂ } изоморфны, если между их дугами и узлами может быть установлено взаимно однозначное соответствие: N ₁ <=> N ₂: A ₁ <=> A ₂.

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

Алгоритм распознавания двух изоморфных графов:

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

2. Выписываем все элементы обоих графов в естественной упорядоченности и определяем пары (x_i, x_j) и (y_i, y_j) для каждого эле-мента, где x_i, y_i - число исходов для каждой вершины графов G₁ и G₂, а x_j, y_j - число заходов для соответствующих графов.

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

4. Выписываем подстановку, которая переводит граф G₁ в граф G₂.

Пример изоморфизма графов.

Граф G1	Граф G2	Изоморфизм между графами G1 и G2	Подстановка изоморфизма f
		f (a) = 1 f (b) = 6 f (c) = 8 f (d) = 3 f (g) = 5 f (h) = 2 f (i) = 4 f (j) = 7

Определение. Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Определение. Орграф D1 называется подразбиением орграфа D2, если орграф D1 можно получить из D2 путем последовательного применения операции подразбиения дуг.

Определение. Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.

Аналогично определяется подразбиение графа и гомеоморфизм графов.