WikiSort.ru - Не сортированное

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

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

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

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

См. также

• АТ-группа

Примечания