Изоморфизм

На рис. 1.8 изображены два графа с одним и тем же множеством вершин . При внимательном рассмотрении можно обнаружить, что это разные графы - в левом имеется ребро , в правом же такого нет. В то же время, если не обращать внимания на наименования вершин, то эти графы явно одинаково устроены: каждый из них - цикл из четырех вершин. Во многих случаях при исследовании строения графов имена или номера вершин не играют роли, и такие графы, один из которых получается из другого переименованием вершин, удобнее было бы считать одинаковыми. Для того чтобы это можно было делать "на законном основании", вводится понятие изоморфизма графов.

Рис. 1.8.

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

Тот факт, что графы и изоморфны, записывается так: .

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

(вершина графа )
(вершина графа )

Заметим, что в этом примере есть и другие изоморфизмы первого графа на второй.

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

Изоморфизм - бинарное отношение на множестве графов. Очевидно, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.

Операции над графами

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

Локальные операции

Простейшая операция - удаление ребра. При удалении ребра сохраняются все вершины графа и все его ребра, кроме удаляемого. Обратная операция - добавление ребра.

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

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

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

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

Рис. 1.10.