1.8. Изоморфизм и 2-изоморфизм

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

Рис. 1.17. Изоморфные графы. а —

Рис. 1.18. 1-изоморфизм. а — в — граф после расщепления и, в г — граф после расщепления

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

Согласно данному определению графы, представленные на рис. рис. 1.17, изоморфны. Соответствие между множествами их вершин и ребер следующее:

Рассмотрим разделимые графы представленные на рис. 1.18, а, б. Эти графы не изоморфны. Предположим, что мы так «расщепили» точку сочленения в на две вершины, что получились два реберно-непересекающихся графа на рис. Если мы выполним подобное расщепление в точке сочленения то получим два реберно-непересекающихся графа, приведенных на рис. 1.18, г. Легко убедиться, что графы на рис. 1.18, в, г изоморфны. Таким образом, графы стали изоморфными после расщепления точек сочленения. Такие графы называются -изоморфными.

Далее определим -изоморфизм как более общий тип изоморфизма. Два графа являются -изоморфными, если они становятся изоморфными после применения следующих операций:

1. «Расщепление» точки сочленения в и (или) в на две вершины, такое, что получаются два реберно-непересекающихся графа.

2. Если один из графов, например состоит из двух подграфов имеющих точно две общие вершины то выполнение перестановки этих вершин осуществляется в одном из подграфов. (Геометрически эта операция эквивалентна такому «переворачиванию» одного из подграфов G, и что общие вершины в нем меняются местами.)

Рассмотрим графы на рис. 1.19, а, б. После расщепления вершины и выполнения операции «переворачивания» с переменой мест вершин мы получим граф представленный на рис. 1.19, в. Расщепление вершины приводит к графу изображенному на рис. 1.19, г. Графы изоморфны. Следовательно, графы являются -изоморфными.

Важный результат по -изоморфным графам формулируется в следующей теореме:

Теорема 1.7. Два графа G, и являются 2-изоморфными тогда и только тогда, когда существует взаимно-однозначное соответствие между множествами их ребер, такое, что циклы в одном графе соответствуют циклам в другом.

Рис. 1.19. 2-изоморфизм. а —

Тот факт, что циклы в будут соответствовать циклам в , когда -изоморфны, достаточно очевиден. Однако доказательство обратного слишком длинно, чтобы обсуждать его здесь. Оно приведено в оригинальной работе [1.1], посвященной 2-изоморфным графам.