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

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

ФормулировкаПравить

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

ПоясненияПравить

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

ПримечанияПравить

↑ 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> Архивная копия от 11 июня 2010 на Wayback Machine
↑ 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> Архивная копия от 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ó, Handbook of Combinatorics, vol. I, North-Holland, с. 1447—1540, <http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps> Архивная копия от 11 июня 2010 на Wayback Machine

[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> Архивная копия от 5 июня 2011 на Wayback Machine.

[1]

[2]