Теорема Фрухта (Mykjybg Sjr]mg)

Перейти к навигации Перейти к поиску

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

Формулировка

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

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

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

Примечания

[править | править код]
  1. Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Handbook of Combinatorics, vol. I, North-Holland, pp. 1447—1540, Архивировано 11 июня 2010 Архивная копия от 11 июня 2010 на Wayback Machine
  2. Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (нем.), 6: 239—250, ISSN 0010-437X, Zbl 0020.07804, Архивировано из оригинала 5 июня 2011, Дата обращения: 9 мая 2014.

Литература

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