Асимметричный график
- В теории графов асимметричный граф не имеет нетривиальных симметрий.
- Автоморфизм графа — перестановка вершин с условием смежности любых двух вершин при перестановке.
- Тождественное отображение графа на себя является тривиальным автоморфизмом.
- Асимметричный граф не имеет других автоморфизмов.
- Примеры наименьших асимметричных нетривиальных графов имеют 6 вершин.
- Класс асимметричных графов замкнут в отношении дополнений.
- Любой асимметричный граф с n вершинами может быть сделан симметричным, добавляя и удаляя не более n / 2 + o (n) ребер.
- Доля графов с n вершинами с нетривиальным автоморфизмом стремится к нулю при росте n.
- Почти все деревья симметричны, в отличие от графов.
Полный текст статьи: