Симметричный граф: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
G2ii2g (обсуждение | вклад) →Примеры: орфография |
Добавление ссылок на электронные версии книг (20231223)) #IABot (v2.0.9.5) (GreenC bot |
||
| (не показано 5 промежуточных версий 2 участников) | |||
| Строка 20: | Строка 20: | ||
| автор = Chris Godsil, Gordon Royle |
| автор = Chris Godsil, Gordon Royle |
||
| заглавие = Algebraic Graph Theory |
| заглавие = Algebraic Graph Theory |
||
| ссылка = https://archive.org/details/algebraicgraphth00gods |
|||
| место =New York |
| место =New York |
||
| издательство =Springer |
| издательство =Springer |
||
| год =2001 |
| год =2001 |
||
| страницы =59 |
| страницы =[https://archive.org/details/algebraicgraphth00gods/page/n79 59] |
||
| isbn =0-387-95220-9 |
| isbn =0-387-95220-9 |
||
}}</ref> Такие графы иногда называют также '''1-транзитивными относительно дуг'''<ref name="godsil"/> или '''флаг-транзитивными'''.<ref name="babai">{{книга |
}}</ref> Такие графы иногда называют также '''1-транзитивными относительно дуг'''<ref name="godsil"/> или '''флаг-транзитивными'''.<ref name="babai">{{книга |
||
|автор |
|автор = L Babai |
||
|ответственный = R Graham, M Groetschel, L Lovasz |
|ответственный = R Graham, M Groetschel, L Lovasz |
||
|заглавие |
|заглавие = Handbook of Combinatorics |
||
|вклад |
|вклад = Automorphism groups, isomorphism, reconstruction |
||
|url |
|url = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |
||
|год |
|год = 1996 |
||
|издательство |
|издательство = Elsevier |
||
|ссылка= |
|ссылка = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |
||
|archive-date = 2010-06-11 |
|||
|archive-url = https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |
|||
}}</ref> |
}}</ref> |
||
| Строка 42: | Строка 45: | ||
| автор =Gross, J.L. and Yellen, J. |
| автор =Gross, J.L. and Yellen, J. |
||
| заглавие =Handbook of Graph Theory |
| заглавие =Handbook of Graph Theory |
||
| ссылка =https://archive.org/details/handbookofgrapht0000unse/page/491 |
|||
| издательство =CRC Press |
| издательство =CRC Press |
||
| год =2004 |
| год =2004 |
||
| Строка 48: | Строка 52: | ||
}}</ref> Наименьший связный полутранзитивный граф — это [[граф Холта]], имеющий степень 4 и 27 вершин.<ref name="biggs" /><ref>{{статья |
}}</ref> Наименьший связный полутранзитивный граф — это [[граф Холта]], имеющий степень 4 и 27 вершин.<ref name="biggs" /><ref>{{статья |
||
| заглавие = A graph which is edge transitive but not arc transitive |
| заглавие = A graph which is edge transitive but not arc transitive |
||
| ссылка = https://archive.org/details/sim_journal-of-graph-theory_summer-1981_5_2/page/201 |
|||
| автор = Derek F. Holt |
| автор = Derek F. Holt |
||
| издание = Journal of Graph Theory |
| издание = Journal of Graph Theory |
||
| Строка 62: | Строка 67: | ||
== Примеры == |
== Примеры == |
||
Сочетание условий симметрии с условием, что граф [[Кубический граф|кубический]] (то есть все вершины имеют степень 3), порождает достаточно сильное условие, чтобы все такие графы были достаточно редки и их можно было бы перечислить. '''Список Фостера''' и его расширения дают такие списки.<ref>{{не переведено 5|Кондер, Марстон|Марстон Кондер||Marston Conder}}, ''[http://www.math.auckland.ac.nz/~conder/preprints/cubic768.ps Trivalent symmetric graphs on up to 768 vertices],'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41-63</ref> Список Фостера был начат в 1930-х годах [[Фостер, Рональд|Рональдом Фостером]] во время его работы в [[Bell Labs]],<ref>Foster, R. M. «Geometrical Circuits of Electrical Networks.» ''[[Transactions of the American Institute of Electrical Engineers]]'' '''51''', 309—317, 1932.</ref> и в 1988 (когда Фостеру было 92<ref name="biggs"/>) список Фостера (список всех симметричных кубических графов вплоть до 512 вершин, известных на тот момент) был опубликован в виде книги.<ref>«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</ref> Первые тринадцать элементов списка — кубические симметричные графы, имеющие до 30 вершин<ref>Biggs, p. 148</ref><ref name="F26A">Weisstein, Eric W., «[http://mathworld.wolfram.com/CubicSymmetricGraph.html Cubic Symmetric Graph]», from Wolfram MathWorld.</ref> (десять из них — [[Дистанционно-транзитивный граф|дистанционно-транзитивные]]), |
Сочетание условий симметрии с условием, что граф [[Кубический граф|кубический]] (то есть все вершины имеют степень 3), порождает достаточно сильное условие, чтобы все такие графы были достаточно редки и их можно было бы перечислить. '''Список Фостера''' и его расширения дают такие списки.<ref>{{не переведено 5|Кондер, Марстон|Марстон Кондер||Marston Conder}}, ''[http://www.math.auckland.ac.nz/~conder/preprints/cubic768.ps Trivalent symmetric graphs on up to 768 vertices] {{Wayback|url=http://www.math.auckland.ac.nz/~conder/preprints/cubic768.ps |date=20110615124127 }},'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41-63</ref> Список Фостера был начат в 1930-х годах [[Фостер, Рональд|Рональдом Фостером]] во время его работы в [[Bell Labs]],<ref>Foster, R. M. «Geometrical Circuits of Electrical Networks.» ''[[Transactions of the American Institute of Electrical Engineers]]'' '''51''', 309—317, 1932.</ref> и в 1988 (когда Фостеру было 92<ref name="biggs"/>) список Фостера (список всех симметричных кубических графов вплоть до 512 вершин, известных на тот момент) был опубликован в виде книги.<ref>«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</ref> Первые тринадцать элементов списка — кубические симметричные графы, имеющие до 30 вершин<ref>Biggs, p. 148</ref><ref name="F26A">Weisstein, Eric W., «[http://mathworld.wolfram.com/CubicSymmetricGraph.html Cubic Symmetric Graph] {{Wayback|url=http://mathworld.wolfram.com/CubicSymmetricGraph.html |date=20110105115900 }}», from Wolfram MathWorld.</ref> (десять из них — [[Дистанционно-транзитивный граф|дистанционно-транзитивные]]), |
||
приведены ниже в таблице |
приведены ниже в таблице |
||
{{якорь|Список Фостера}} |
{{якорь|Список Фостера}} |
||
| Строка 108: | Строка 113: | ||
* [[Алгебраическая теория графов]] |
* [[Алгебраическая теория графов]] |
||
* {{не переведено 5|Галерея именованных графов|Галерея именованных графов|en|Gallery of named graphs}} |
* {{не переведено 5|Галерея именованных графов|Галерея именованных графов|en|Gallery of named graphs}} |
||
* [[Правильная карта (теория графов)|Правильная карта]] |
|||
* {{не переведено 5|Регулярное отображение (теория графов)|Регулярное отображение||Regular map (graph theory)}} |
|||
== Примечания == |
== Примечания == |
||
Текущая версия от 00:31, 24 декабря 2023
Симметричный граф (или транзитивный относительно дуг граф) — граф 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.
 | Для улучшения этой статьи желательно:
|