Симметричный граф
Симметричный граф (или транзитивный относительно дуг граф) — граф 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 2 3 4 5 6 Biggs, Norman. Algebraic Graph Theory. — 2nd. — Cambridge: Cambridge University Press, 1993. — С. 118—140. — ISBN 0-521-45897-8.
- ↑ 1 2 3 Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer, 2001. — С. 59. — ISBN 0-387-95220-9.
- ↑ 1 2 3 L Babai. Handbook of Combinatorics / R Graham, M Groetschel, L Lovasz. — Elsevier, 1996. Архивировано 11 июня 2010 года.
- ↑ Bouwer, Z. «Vertex and Edge Transitive, But Not 1-Transitive Graphs.» Canad. Math. Bull. 13, 231—237, 1970.
- ↑ Gross, J.L. and Yellen, J. Handbook of Graph Theory. — CRC Press, 2004. — С. 491. — ISBN 1-58488-090-2.
- ↑ 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..
- ↑ Марстон Кондер, Trivalent symmetric graphs on up to 768 vertices Архивная копия от 15 июня 2011 на Wayback Machine, J. Combin. Math. Combin. Comput, vol. 20, pp. 41-63
- ↑ Foster, R. M. «Geometrical Circuits of Electrical Networks.» Transactions of the American Institute of Electrical Engineers 51, 309—317, 1932.
- ↑ «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
- ↑ Biggs, p. 148
- ↑ 1 2 Weisstein, Eric W., «Cubic Symmetric Graph Архивная копия от 5 января 2011 на Wayback Machine», from Wolfram MathWorld.
Ссылки[править | править код]
- Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
- Trivalent (cubic) symmetric graphs on up to 2048 vertices. Marston Conder, August 2006, retrieved 2009-08-20.
 | Для улучшения этой статьи желательно:
|