Матрицы заболеваемости

Question

Перестановка любых двух строк или столбцов в матрице инцидентов просто соответствует перемаркировке вершин и ребер одного и того же графа. Наоборот, два графа X и Y изоморфны тогда и только тогда, когда их матрицы инцидентности A(X) и A(Y) отличаются только перестановками строк и столбцов.

Может кто-нибудь объяснить мне, что это значит, на примере. Что именно означает "перестановка любых двух строк или столбцов" через слух?

Answer 1

"Перестановка" здесь означает "обмен". Рассмотрим следующую матрицу инцидентности узел-узел:

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 и наоборот. Это означает, что оба графа "идентичны с точностью до переименования вершин", т.е. они изоморфны.