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