Матрица смежности для неориентированного графа

Информация о структуре графа может быть задана матрицей бинарного отношения.

Матрица смежности для неориентированного графа – это матрица с элементами

^а_{ij = ,}(1,если вершина х_i смежна с вершиной x _j, и 0, если вершина х_i не смежнас x _j.,)

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

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

Два графа называются изоморфными (от греч. «изос» — «равный» и «морфе» — «вид», «фор­ма»), если между их вершинами можно уста­новить взаимно однозначное соответствие при котором вершинам, соединённым ребром, соответствуют вершины, также соединённые ребром.

Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строк и столбцов (т.е. одновременно с перестановкой i-ой и j-ой строк переставляются i-й и j-й столбцы).