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

Теорема Фрухта — утверждение об изоморфизме каждой конечной группы группе автоморфизмов конечного неориентированного графа. Была сформулирована в 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>.

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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>.