Доказать, что AutG={s€Sn: MsA(G)=A(G)Ms}, где Ms - подстановочная матрица, соответствующая постановке s, а A(G) - матрица смежности графа G.

задан 10 Ноя '21 17:22

10|600 символов нужно символов осталось
0

Автоморфизм задаёт подстановку на множестве вершин графа. При этом, если вершины были соединены, то их образы также соединены ребром графа.

В матрице M(s)A строки пойдут в порядке s(1), ... , s(n), то есть первая строка матрицы A встанет на s(1)-е место, и так далее. У матрицы AM(s) поменяются местами столбцы: столбец с номером s(1) станет первым, и так далее. Это всё следует из правил умножения матриц.

Если в матрице A элемент a(i,j) был равен 1, то у матрицы M(s)A он перейдёт в элемент a(s(i),j)). Это элемент j-го столбца матрицы, равной AM(s), поэтому у A он стоял в той же строке, но в столбце с номером s(j). Таким образом, a(s(i),s(j))=1. То же верно для матричных элементов, равных 0.

Мы показали, что если вершины i, j были соединены ребром в графе, то их образы при подстановке, то есть s(i), s(j), также соединены. То же для не соединённых вершин. Это верно для произвольных i, j, то есть s индуцирует автоморфизм графа. Рассуждение верно в ту и другую сторону.

ссылка

отвечен 10 Ноя '21 23:22

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,059
×239

задан
10 Ноя '21 17:22

показан
104 раза

обновлен
10 Ноя '21 23:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru