Симметричный граф: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м Неактуальный шаблон
м Неактуальный шаблон
Строка 90: Строка 90:
|}
|}


Другие хорошо известные симметричные кубические графы — это [[Граф Дика]], {{не переведено 5|Граф Фостера|граф Фостера||Foster graph}} и {{не переведено 5|Граф Бигса–Смита|граф Бигса–Смита||Biggs–Smith graph}}. Десять дистанционно-транзитивных графов перечислены выше. Вместе с {{не переведено 5|Граф Фостера|графом Фостера||Foster graph}} и {{не переведено 5|Граф Бигса–Смита|графом Бигса–Смита||Biggs–Smith graph}} это единственные дистанционно-транзитивные графы.
Другие хорошо известные симметричные кубические графы — это [[Граф Дика]], [[граф Фостера]] и {{не переведено 5|Граф Бигса–Смита|граф Бигса–Смита||Biggs–Smith graph}}. Десять дистанционно-транзитивных графов перечислены выше. Вместе с [[Граф Фостера|графом Фостера]] и {{не переведено 5|Граф Бигса–Смита|графом Бигса–Смита||Biggs–Smith graph}} это единственные дистанционно-транзитивные графы.


Некубические симметричные графы включают [[Граф-цикл|циклы]] (степени 2), [[Полный граф|полные графы]] (степени 4 и выше с 5 и более вершинами), [[Граф гиперкуба|графы гиперкубов]] (степени 4 и выше с 16 и более вершинами) и графы, образованные вершинами и рёбрами [[Октаэдр|октаэдра]], [[Икосаэдр|икосаэдра]], [[Кубооктаэдр|кубооктаэдра]] и [[Икосододекаэдр|икосододекаэдра]]. [[Граф Радо]] даёт пример симметричного графа с бесконечным числом вершин и бесконечной степенью.
Некубические симметричные графы включают [[Граф-цикл|циклы]] (степени 2), [[Полный граф|полные графы]] (степени 4 и выше с 5 и более вершинами), [[Граф гиперкуба|графы гиперкубов]] (степени 4 и выше с 16 и более вершинами) и графы, образованные вершинами и рёбрами [[Октаэдр|октаэдра]], [[Икосаэдр|икосаэдра]], [[Кубооктаэдр|кубооктаэдра]] и [[Икосододекаэдр|икосододекаэдра]]. [[Граф Радо]] даёт пример симметричного графа с бесконечным числом вершин и бесконечной степенью.

Версия от 14:31, 6 декабря 2014

Граф Петерсена является (кубическим) симметричным графом. Любую пару смежных вершин можно перевести в другую пару автоморфизмом, поскольку любое кольцо из пяти вершин можно перевести в любое такое же.

Симметричный граф (или транзитвный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм:

f : V(G) → V(G)

такой, что:

f(u1) = u2 and f(v1) = v2.[1]

Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин (таким образом, на всех рёбрах как если бы они имели ориентацию).[2] Такие графы иногда называют также 1-транзитивными относительно дуг[2] или флаг-транзитивными.[3]

По определению симметричные графы без изолированных вершин должны быть также вершинно-транзитивными.[1] Поскольку по определению выше рёбра можно перевести из одного в другое, симметричные графы должны быть также рёберно-транзитивными. Однако, рёберно-транзитивный граф не обязательно симметричен, поскольку a—b может быть переведён в c—d, но не в d—c. Полусимметричные графы?!, например, являются рёберно-транзитивными и регулярными, но не вершинно-транзитивными.

Любой связный симметричный граф должен быть как вершинно-транзитивен, так и рёберно-транзитивен, и обратное верно для графов нечётной степени.[3] Однако для чётных степеней существуют связные одновременно вершинно-транзитивные и рёберно-транзитивные графы, но не симметричные.[4] Такие графы называются полутранзитивными?!.[5] Наименьший связный полутранзитивный граф — это граф Холта, имеющий степень 4 и 27 вершин.[1][6] Запутывает то, что некоторые авторы используют термин «симметричный граф» для графов, которые одновременно являются вершинно-транзитивными и рёберно-транзитивными. Такое определение включает полутранзитивные графы, которые исключены определением выше.

Дистанционно-транзитивный граф — это граф, в котором вместо единичного расстояния смежные вершины находятся на одном и том же фиксированном расстоянии. Такие графы по определению симметричны.[1]

t-дуга определяется как последовательность t+1 вершин, таких что любые две последовательные вершины смежны, и повторение вершин может произойти не раньше чем через 2 шага. Граф называется t-транзитивным, если группа автоморфизмов действует транзитивно на t-дуги, но не на (t+1)-дуги. Поскольку 1-дуги — это просто рёбра, любой симметричный граф степени 3 и более должен быть t-транзитивным для некоторого t, и значение t можно использовать для классификации графов. Куб является 2-транзитивным, например.[1]

Примеры

Сочетание условий симметрии с условием, что граф кубический (то есть все вершины имеют степень 3), порождает достаточно сильное условие, чтобы все такие графы были достаточно редки и их можно было бы перечислить. Список Фостера и его расширения дают такие списки.[7] Список Фостера был начат в 1930-х годах Р.М. Фостером[англ.] во время его работы в Bell Labs,[8] и в 1988 (когда Фостеру было 92[1]) список Фостера (список всех симметричных кубических графов вплоть до 512 вершин, известных на тот момент) был опубликован в виде книги.[9] Первые тринадцать элементов списка — кубические симметричные графы, имеющие до 30 вершин[10][11] (десять из них — дистанционно-транзитивные), приведены ниже в таблице

Вершины Диаметр Обхват Граф Примечания
4 1 3 полный граф K4 дистанционно транзитивен, 2-транзитивен
6 2 4 полный двудольный граф K3,3 дистанционно транзитивен, 3-транзитивен
8 3 4 вершины и рёбра куба дистанционно транзитивен, 2-транзитивен
10 2 5 граф Петерсена дистанционно транзитивен, 3-транзитивен
14 3 6 граф Хивуда дистанционно транзитивен, 4-транзитивен
16 4 6 граф Мёбиуса-Кантора 2-транзитивен
18 4 6 граф Паппа дистанционно транзитивен, 3-транзитивен
20 5 5 вершины и рёбра додекаэдра дистанционно транзитивен, 2-транзитивен
20 5 6 граф Дезарга дистанционно транзитивен, 3-транзитивен
24 4 6 граф Науру?! (обобщённый граф Петерсена G(12,5)) 2-транзитивен
26 5 6 граф F26A?![11] 1-транзитивен
28 4 7 граф Коксетера?! дистанционно транзитивен, 3-транзитивен
30 4 8 Граф Татта — Коксетера дистанционно транзитивен, 5-транзитивен

Другие хорошо известные симметричные кубические графы — это Граф Дика, граф Фостера и граф Бигса–Смита[англ.]. Десять дистанционно-транзитивных графов перечислены выше. Вместе с графом Фостера и графом Бигса–Смита[англ.] это единственные дистанционно-транзитивные графы.

Некубические симметричные графы включают циклы (степени 2), полные графы (степени 4 и выше с 5 и более вершинами), графы гиперкубов (степени 4 и выше с 16 и более вершинами) и графы, образованные вершинами и рёбрами октаэдра, икосаэдра, кубооктаэдра и икосододекаэдра. Граф Радо даёт пример симметричного графа с бесконечным числом вершин и бесконечной степенью.

Свойства

Вершинная связность симметричного графа всегда равна степени d.[3] Для контраста, для общих вершинно-транзитивных графов вершинная связность ограничена снизу числом 2(d+1)/3.[2]

t-транзитивный граф степени 3 и выше имеет обхват по меньшей мере 2(t-1). Однако не существует конечных t-транзитивных графов степени 3 и выше для t ≥ 8. В случае степени, в точности равной трём (кубические симметричные графы), нет графов для t ≥ 6.

См. также

Примечания

  1. ↑ 1 2 3 4 5 6 Biggs, Norman. Algebraic Graph Theory. — 2nd. — Cambridge: Cambridge University Press, 1993. — С. 118–140. — ISBN 0-521-45897-8.
  2. ↑ 1 2 3 Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer, 2001. — С. 59. — ISBN 0-387-95220-9.
  3. ↑ 1 2 3 L Babai. Handbook of Combinatorics / R Graham, M Groetschel, L Lovasz. — Elsevier, 1996.
  4. ↑ Bouwer, Z. «Vertex and Edge Transitive, But Not 1-Transitive Graphs.» Canad. Math. Bull. 13, 231—237, 1970.
  5. ↑ Gross, J.L. and Yellen, J. Handbook of Graph Theory. — CRC Press, 2004. — С. 491. — ISBN 1-58488-090-2.
  6. ↑ Derek F. Holt. A graph which is edge transitive but not arc transitive // Journal of Graph Theory. — 1981. — Т. 5, вып. 2. — С. 201–204. — doi:10.1002/jgt.3190050210..
  7. ↑ Марстон Кондер[англ.], Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41-63
  8. ↑ Foster, R. M. «Geometrical Circuits of Electrical Networks.» Transactions of the American Institute of Electrical Engineers 51, 309—317, 1932.
  9. ↑ «The Foster Census: R.M. Foster’s Census of Connected Symmetric Trivalent Graphs», by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2
  10. ↑ Biggs, p. 148
  11. ↑ 1 2 Weisstein, Eric W., «Cubic Symmetric Graph», from Wolfram MathWorld.

Ссылки

Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Симметричный_граф&oldid=67188644