@Feor_slen

В чем суть ассиметричного графа?

Добрый день! Изучив некоторую информацию я для себя попытался объяснить, что ассиметричный граф это граф, у которого каждая вершина имеет разное количество связей, то есть оне незаменяема...
Но не уверен в корректности формулировки. Прав ли я? Если нет то укажите, пожалуйста, где. И по возможности расскажите все, что вам об этом известно про свойства/признаки таких графов.

Вики говорит:
В теории графов, разделе математики, неориентированный граф называется асимметричным графом, если он не имеет нетривиальных симметрий.

Формально, автоморфизм графа - это перестановка p его вершин, обладающая свойством, что любые две вершины u и v смежны тогда и только тогда, когда p(u) и p(v) смежны. Отображение идентичности графа всегда является автоморфизмом и называется тривиальным автоморфизмом графа. Асимметричный граф - это граф, для которого нет других автоморфизмов.


Материалы преподователя говорят:

Граф называется ассиметричным только тогда когда обладает тождественным автоморфизмом.


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

Тезис выше опровергли примеры которые я посмотрел

Заранее спасибо.
  • Вопрос задан
  • 54 просмотра
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Суть в том, что в графе нет одинаковых вершин или групп вершин. Их нельзя как-то переставить, что граф останется выглядеть точно так же. Вот пример граф из 4 вершин в виде квадрата. Его крутить можно как угодно и отражать - он выглядит точно так же - квадрат он и есть квадрат. А вот треугольник из одной вершины которого торчит путь длины 1, а из другой вершины - путь длины 2 - он несимметричный. Каждая вершина по своему уникальна. Одна вершина на треугольнике имеет степень 2. Одна имеет степень 3 и до ближайшей вершины-листа путь длины 1, Одна имеет степень 3 и до ближайшей вершины листа путь длины 2. Есть только одна вершина степени 2 не на цикле. Оставшиеся 2 вершины имеют степени 1, но от одной до цикла путь длины 1, а от другой - 2. Вы эти вершины как-то поменяйте местами и у вас граф будет выглядеть по другому.

Не обязательно все вершины должны иметь разную степень. Но их нельзя поменять местами, потому что они связаны с другими вершинам по разному.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы