11. Изоморфизм и гомеоморфизм графов, методы доказательства изоморфности и неизоморфности графов.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

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

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

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

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

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

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