Перестановка любых двух строк или столбцов в матрице инцидентности просто соответствует переименованию вершин и ребер одного и того же графа. И наоборот, два графа X и Y изоморфны тогда и только тогда, когда их матрицы инцидентности A(X) и A(Y) отличаются только перестановками строк и столбцов.
Может кто-нибудь объяснить мне, что это значит, с примером. Что именно означает «перестановка любых двух строк или столбцов»?
«Перестановка» здесь означает «обмен». Рассмотрим следующую матрицу инцидентности между узлами:
0 1 0
0 0 1
1 0 0
Он определяет граф с вершинами 0, 1, 2, где ребра образуют окружность 0-1-2-0. Если поменять местами первые две строки, получим
0 0 1
0 1 0
1 0 0
где круг 0-2-1-0. Этот граф получается из исходного графа путем перемаркировки 1 на 2 и наоборот. Это означает, что оба графа «одинаковы с точностью до переименования вершин», т. е. изоморфны.
