Automorphism

Материал из WikiGrapp
Версия от 16:10, 19 декабря 2011; KVN (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Automorphismавтоморфизм (ор)графа.

1. For an undirected graph, see Isomorphic graphs.

2. For a directed graph, automorphism is a permutation [math]\displaystyle{ \,\alpha }[/math] of [math]\displaystyle{ \,V(G) }[/math] such that the number of [math]\displaystyle{ \,(x,y) }[/math]-edges is the same as the number of [math]\displaystyle{ (\,\alpha(x), \alpha(y)) }[/math]-edges [math]\displaystyle{ (x,y \in V(G)) }[/math]. We also speak of the automorphism of a graph [math]\displaystyle{ \,G }[/math] with colored edges. This means a permutation [math]\displaystyle{ \,\alpha }[/math] such that the number of [math]\displaystyle{ \,(x,y) }[/math]-edges is the same as the number of [math]\displaystyle{ (\,\alpha(x), \alpha(y)) }[/math]-edges with any given color.

The set of all automorphisms of a (di)graph forms a permutation group [math]\displaystyle{ \,A(G) }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.