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

Изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. группой (или иногда вершинной группой) графа G, и группу подстановок ребер Г 1(G), наз. реберной группой графа G. Реберная п вершинная группы графа G без петель и кратных ребер изоморфны тогда и только тогда, когда граф G имеет не более одной изолированной вершины и никакая его компонента связности не является изолированным ребром. Для каждой конечной группы Fсуществует граф, группа автоморфизмов к-рого изоморфна F. В то же время существуют группы подстановок на множестве из пэлементов, не являющиеся вершинной группой никакого графа с пвершинами. С Г. а. можно связать различные типы и меры симметрии графа. Асимметричным называется граф, не имеющий автоморфизмов, отличных от тождественного. При n Ю 4 почти все графы с пвершинами являются асимметричными. Лит.:[1] Харари Ф., Теория графов, пер. с англ., М., 1973. В. Б. Алексеев.