ГРАФА АВТОМОРФИЗМ

ГРАФА АВТОМОРФИЗМ - изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа G порождают группу подстановок вершин Г(G), наз. группой (или иногда вершинной группой) графа G, и группу подстановок ребер Г₁(G), наз. реберной группой графа G. Реберная и вершинная группы графа G без петель и кратных ребер изоморфны тогда и только тогда, когда граф G имеет не более одной изолированной вершины и никакая его компонента связности не является изолированным ребром. Для каждой конечной группы F существует граф, группа автоморфизмов к-рого изоморфна F. В то же время существуют группы подстановок на множестве из n элементов, не являющиеся вершинной группой никакого графа с n вершинами. С Г. а. можно связать различные типы и меры симметрии графа. Асимметричным называется граф, не имеющий автоморфизмов, отличных от тождественного. При n → ∞ почти все графы с n вершинами являются асимметричными.

Лит.: [1] Xарари Ф., Теория графов, пер. с англ., М., 1973.

В. Б. Алексеев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.