Теорема Фрухта

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

Теорема Фрухта — утверждение об изоморфизме каждой конечной группы группе автоморфизмов конечного неориентированного графа. Была сформулирована в 1936 году Бабаи[1] и доказана в 1939 году Фрухтом[2].

Формулировка[править | править код]

Каждая конечная группа изоморфна группе автоморфизмов конечного неориентированного графа.

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

Автоморфизмом графа называется любая подстановка множества его вершин, являющаяся изморфизмом на себя.

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

  1. Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin & Lovász, László, Handbook of Combinatorics, vol. I, North-Holland, сс. 1447—1540, <http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps> 
  2. Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica Т. 6: 239—250, ISSN 0010-437X, <http://www.numdam.org/item?id=CM_1939__6__239_0> .

Литература[править | править код]

  • Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — С. 341-349. — ISBN 5-7038-2886-4.