Есть некоторый граф на n вершинах (Пусть для наглядности n = 5). Все его вершины можно расположить в ряд, граф от этого не меняется. Граф называется изоморфным, если существует биекция, при которой ребра сохраняются. Правильно ли я понимаю, что для некоторого графа, можно взять любую перестановку (перестановка биективна), значит тогда новый граф из этой перестановки будет изоморфен изначальному.

В качестве примера:

alt text

Это соответствует перестановке:

$$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 2 & 3 & 1 \end{pmatrix} $$

С таким же успехом можно взять любую другую перестановку, а значит количество изоморфных графов это n! (Естественно, это не изменение ребер графа, а изменение меток вершин, т.е. можно было бы рассматривать биекции из {1,2,3,4,5} в {a,b,c,d,e}, идея была бы такая же)

Я предполагаю, что это рассуждение где-то концептуально неправильное и есть какое-то непонимание изоморфизма, но конкретную ошибку в рассуждениях я найти не могу.

Объясните, пожалуйста, в чем я неправ.

задан 29 Сен '19 14:37

Понимание изоморфизма правильное. Все графы, изоморфные данному, именно так и выглядят. Фактически, граф один и тот же, но мы по-разному размечаем его вершины, что можно сделать n! способами. Не совсем точен лишь тезис о том, что "изоморфных графов n!". Лучше сказать, что из одного графа получается n! его изоморфных копий.

Здесь для лучшего понимания можно рассмотреть такой пример. Пусть вершины одного графа нарисованы в ряд, вершины слева направо занумерованы. Нарисуем рядом n вершин, расположенных как попало, и занумерованных числами от 1 до n хаотично. Проведём нужные соединения.

(29 Сен '19 14:58) falcao

(продолжение) Имеется в виду, что если в первом графе есть ребро i-j, то добавляем его во втором. Получится копия первого графа, то есть изоморфный граф. Теперь сотрём на втором графе номера вершин. Тогда, если мы их забудем, факт изоморфности подтвердить окажется несколько нелегко. Нужно перебирать все n! разметок и проверять, подходит ли очередная разметка. Если все случаи перебрали, но подходящего не нашли, то графы не изоморфны. Это я к тому, что если есть две картинки, то по ним сходу бывает трудно сказать, изоморфны ли графы (проблема изоморфизма).

(29 Сен '19 15:01) falcao

И при наличии циклов, кратных ребер или нескольких компонент связанности ситуация не меняется, имеем так же n! изоморфных копий данного графа. Правильно?

(29 Сен '19 15:09) MaximH

@MaximH: специфика графа не играет роли. В любом случае, n вершин можно пронумеровать n! способами, независимо от наличия/отсутствия соединений. Что-то интересное может появиться при таком подходе. Пусть дан граф с n вершинами. Пронумеруем их от 1 до n. Такой объект называется размеченным графом. Два размеченных графа называются изоморфными (как размеченные), если для любых i,j, соединений в одном и другом графе между i-й и j-й вершиной одно и то же количество. Как графы, они все изоморфны. Рассмотрим пример: a соединена с b, и b соединена с c. Разметок 6, но разных размеченных графов 3.

(29 Сен '19 16:24) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×544
×66

задан
29 Сен '19 14:37

показан
198 раз

обновлен
29 Сен '19 16:24

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

по почте:

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

по RSS:

Ответы

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

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