Автоморфизм графа

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Наименьшее асимметрическое дерево
Наименьший асимметрический граф

Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность.[1] Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной:

Реберная и вершинная группы графа изоморфны тогда и только тогда, когда имеется не более одной изолированной вершины, и нет компонент связности состоящих из единственного ребра.[2]

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

Для любой конечной группы найдется такой конечный неориентированный граф, что его группа автоморфизмов изоморфна данной.[3] Результат получен Р. Фрухтом, в основе доказательства — преобразование цветного графа группы, обобщения графа Кэли.[4][5]

См. также[править | править код]

Примечания[править | править код]

  1. Ф. Харари Теория графов стр. 190
  2. Ф. Харари Теория графов стр. 192
  3. А. И. Белоусов. Дискретная математика. — 4-е изд. — МГТУ имени Н. Э. Баумана, 2006. — С. 349. — 744 с.
  4. Ф. Харари Теория графов стр. 198—201
  5. О. Оре Теория графов стр. 317