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

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

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

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

Пояснения

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

Примечания

↑ 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
↑ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (нем.), 6: 239—250, ISSN 0010-437X, Zbl 0020.07804 Архивная копия от 5 июня 2011 на Wayback Machine.

Литература

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

[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 на Wayback Machine.

[1]

[2]