Теорема Фрухта
Теорема Фрухта є теоремою в алгебричній теорії графів, висловленої в 1936 році Денешем Кенігом і доведеною Робертом Фрухтом в 1939 році. Вона стверджує, що будь-яку скінченну групу можна представити, як групу симетрій скінченного неорієнтованого графу. Більше того, для будь-якої скінченної групи G існує нескінченно багато неізоморфних простих зв'язних графів, для яких група автоморфізму кожного з них ізоморфна G.
Доведення[ред. | ред. код]
Доведення полягає в тому, що граф Келі G, з додаванням кольорів і орієнтацій на його ребрах, має бажану групу автоморфізму. Тому, якщо кожне з цих ребер замінено на відповідний субграф, так що кожний підграф заміни асиметричний, а дві заміни ізоморфні тоді і тільки тоді, коли вони замінюють ребра одного кольору, то неорієнтований граф, створений за допомогою цих замін, також буде мати G як свою групу симетрії.
Розмір графа[ред. | ред. код]
За винятком трьох циклічних груп (порядків 3, 4 і 5) — кожну групу можна представити як симетрію графа, вершини якого мають лише дві орбіти.
Спеціальні види графів[ред. | ред. код]
Існують інші інтерпретації теореми Фрухта, які показують, що деякі обмежені види графів все ще містять достатньо графів для реалізації будь-якої групи симетрії. Наприклад, граф Фрухта, 3-регулярний граф з 12 вершинами і 18 ребрами, не має нетривіальних симетрій, що забезпечує реалізацію цього типу для тривіальної групи. З того факту, що кожен граф може бути реконструйований з часткової множини впорядкування його ребер і вершин, то кожен кінцевий порядок еквівалентний теоремі Біркгофа[en] про скінченну розподільну решітку, кожна група може бути реалізована як дистрибутивна ґратка, а граф ґратки- медіанний граф. Кожну скінченну групу можна реалізувати як групу симетрій сильно регулярного графа. Кожну скінченну групу також можна реалізувати як симетрії графа з числом 2: можна (неправильно) розфарбувати граф двома кольорами, щоб жодна з симетрій графа не зберегла забарвлення.
Проте деякі важливі класи графів не здатні реалізувати всі групи як свої симетрії. Каміль Жордан охарактеризував групи симетрії дерев як найменшу сукупність скінченних груп, що є тривіальними групами. У загальному випадку, будь-яка група графів з замкнутою структурою не здатна представити всі скінченні групи симетріями її графів.
Джерела[ред. | ред. код]
- de Groot, J. (1959), Groups represented by homeomorphism groups, Mathematische Annalen, 138: 80—102, doi:10.1007/BF01369667, ISSN 0025-5831, MR 0119193.
- Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen, Leipzig: Akademische Verlagsgesellschaft, с. 5. As cited by Babai, (1995).
- Sabidussi, Gert (1957), Graphs with given group and given graph-theoretical properties, Canadian Journal of Mathematics, 9: 515—525, doi:10.4153/cjm-1957-060-7, ISSN 0008-414X, MR 0094810, архів оригіналу за 16 липня 2011, процитовано 27 січня 2019.