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

Два графа называются изоморфными(от греч. «изос» – «равный» и «морфе» – «вид», «форма»), если между их вершинами можно установить взаимно однозначное соответствие, сохраняющее смежность, т.е. два графа G(x,u) и G'(x',u') изоморфны, если существует такое взаимно однозначное соответствие j , что если ,то ,где

.

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

Планарность. Плоские графы

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

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

Рис. 3.1.6

Граф G1 (рис. 3.1.6) планарен, он изоморфен плоскому графу G2. Исследование планарности графов составляет одну из задач этой теории. Изучение планарных графов было начато Эйлером. Опираясь на результаты, полученные Эйлером, можно доказать, что графы K₁, K₂, K₃ (рис. 3.1.7) не являются планарными. Заметим, что графы K₁, K₃ изоморфны.

Рис. 3.1.7

Графы, изоморфные указанным графам, также не являются планарными.

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

Говорят, что граф G'(x',u') получен из графа G(x,u) операцией подразделения ребра (x_i,x_j)Îu, если x'=xÈa, u'=[u\(x_i,x_j)]È[(x_i,a)È(a,x_j)]. На рис. 3.1.8 граф G'(x',u') получен из графа G(x,u) подразделением ребра (x₂,x₄), т.е. , , x'=xÈa, u'=[u\(x_2,x₄)]È[(x₂,a)È(a,x₄)].

Рис. 3.1.8

Два графа G₁,G₂ называются гомеоморфными, если существует такой граф G', который может быть получен как из графа G₁, так и из G₂ операцией подразделения ребра конечное число раз. Или: графы G₁ и G₂ гомеоморфны, если существуют изоморфные подразбиения G₁' и G₂'. Графы G₁ и G₂, изображенные на рис. 3.1.9, гомеоморфны.

Рис. 3.1.9

Граф G' может быть получен из графов G₁ и G₂ операцией подразделения ребра, проведенной дважды.

Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного графам K₁ или K₂ (рис. 3.1.7).

Вслед за этим классическим результатом были предложены другие критерии планарности, не рассматриваемые в данном учебном пособии.