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

Два графа G(V, E) и H(W, I) называются изоморфными, если существует взаимно-однозначное соответствие между множествами вершин V, W и множествами ребер E, I, сохраняющее отношение инцидентности.

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

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

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