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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м Неактуальный шаблон
Добавление ссылок на электронные версии книг (20231223)) #IABot (v2.0.9.5) (GreenC bot
 
(не показаны 33 промежуточные версии 14 участников)
Строка 1: Строка 1:
[[Файл:Petersen1 tiny.svg|thumb|200px| [[Граф Петерсена]] является ({{не переведено 5|Кубический граф|кубическим||Cubic graph}}) симметричным графом. Любую пару смежных вершин можно перевести в другую пару [[Автоморфизм|автоморфизмом]], поскольку любое кольцо из пяти вершин можно перевести в любое такое же.]]
[[Файл:Petersen1 tiny.svg|thumb|200px| [[Граф Петерсена]] является ([[Кубический граф|кубическим]]) симметричным графом. Любую пару смежных вершин можно перевести в другую пару [[автоморфизм]]ом, поскольку любое кольцо из пяти вершин можно перевести в любое такое же.]]
В [[Теория графов|теории графов]] [[Граф (математика)|граф]] ''G'' является '''симметричным''' (или '''транзитвным относительно дуг'''), если для любых двух пар смежных вершин ''u''<sub>1</sub>—''v''<sub>1</sub> и ''u''<sub>2</sub>—''v''<sub>2</sub> графа ''G'' имеется [[автоморфизм]]
'''Симметричный граф''' (или ''транзитивный относительно дуг граф'') — [[Граф (математика)|граф]] ''G'', для любых двух пар смежных вершин которого ''u''<sub>1</sub>—''v''<sub>1</sub> и ''u''<sub>2</sub>—''v''<sub>2</sub> имеется [[автоморфизм]]:


:''f'' : ''V''(''G'') → ''V''(''G'')
: ''f'' : ''V''(''G'') → ''V''(''G'')


такой, что
такой, что:


:''f''(''u''<sub>1</sub>) = ''u''<sub>2</sub> and ''f''(''v''<sub>1</sub>) = ''v''<sub>2</sub>.<ref name="biggs">{{книга
: ''f''(''u''<sub>1</sub>) = ''u''<sub>2</sub> and ''f''(''v''<sub>1</sub>) = ''v''<sub>2</sub>.<ref name="biggs">{{книга
| автор =Biggs, Norman
| автор =Biggs, Norman
| заглавие =Algebraic Graph Theory
| заглавие =Algebraic Graph Theory
| издание =2nd
| издание =2nd
| место =Cambridge
| место =Cambridge
| издательство =Cambridge University Press
| издательство =Cambridge University Press
| год =1993
| год =1993
| страницы =118–140
| страницы =118—140
| isbn =0-521-45897-8}}</ref>
| isbn =0-521-45897-8
}}</ref>


Другими словами, граф симметричен, если его [[Группа (математика)|группа]] автоморфизмов [[Действие группы|действует транзитивно]] на упорядоченных парах смежных вершин (таким образом, на всех рёбрах как если бы они имели ориентацию).<ref name="godsil">{{книга
Другими словами, граф симметричен, если его [[Группа (математика)|группа]] автоморфизмов [[Действие группы|действует транзитивно]] на упорядоченных парах смежных вершин (таким образом, на всех рёбрах, как если бы они имели ориентацию).<ref name="godsil">{{книга
| автор = Chris Godsil, Gordon Royle
| автор = Chris Godsil, Gordon Royle
| заглавие = Algebraic Graph Theory
| заглавие = Algebraic Graph Theory
| ссылка = https://archive.org/details/algebraicgraphth00gods
| место =New York
| издательство =Springer
| место =New York
| издательство =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
|автор = L Babai
|ответственный = R Graham, M Groetschel, L Lovasz
| заглавие = Handbook of Combinatorics
|заглавие = Handbook of Combinatorics
| вклад = Automorphism groups, isomorphism, reconstruction
|вклад = Automorphism groups, isomorphism, reconstruction
| url = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps
|url = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps
| год = 1996
|год = 1996
| издательство = Elsevier}}</ref>
|издательство = 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 name="biggs" /> Поскольку по определению выше рёбра можно перевести из одного в другое, симметричные графы должны быть также [[Рёберно-транзитивный граф|рёберно-транзитивными]]. Однако, рёберно-транзитивный граф не обязательно симметричен, поскольку ''a''—''b'' может быть переведён в ''c''—''d'', но не в ''d''—''c''. {{не переведено 5|Полусимметричный граф|Полусимметричные графы||Semi-symmetric graph}}, например, являются рёберно-транзитивными и [[Регулярный граф|регулярными]], но не вершинно-транзитивными.
По определению симметричные графы без изолированных вершин должны быть также [[Вершинно-транзитивный граф|вершинно-транзитивными]].<ref name="biggs" /> Поскольку по определению выше рёбра можно перевести из одного в другое, симметричные графы должны быть также [[Рёберно-транзитивный граф|рёберно-транзитивными]]. Однако рёберно-транзитивный граф не обязательно симметричен, поскольку ''a''—''b'' может быть переведён в ''c''—''d'', но не в ''d''—''c''. [[Полусимметричный граф|Полусимметричные графы]], например, являются рёберно-транзитивными и [[Регулярный граф|регулярными]], но не вершинно-транзитивными.


<!-- {{Graph families defined by their automorphisms}} -->
<!-- {{Graph families defined by their automorphisms}} -->
⚫
Любой связный симметричный граф должен быть как вершинно-транзитивен, так и рёберно-транзитивен, и обратное верно для графов нечётной степени.<ref name="babai" /> Однако для чётных степеней существуют связные одновременно вершинно-транзитивные и рёберно-транзитивные графы, но не симметричные.<ref>Bouwer, Z. «Vertex and Edge Transitive, But Not 1-Transitive Graphs.» Canad. Math. Bull. 13, 231—237, 1970.</ref> Такие графы называются [[Полутранзитивный граф|полутранзитивными]].<ref name="handbook">{{книга

⚫
Любой связный симметричный граф должен быть как вершинно-транзитивен, так и рёберно-транзитивен, и обратное верно для графов нечётной степени.<ref name="babai" /> Однако для чётных степеней существуют связные одновременно вершинно-транзитивные и рёберно-транзитивные графы, но не симметричные.<ref>Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.</ref> Такие графы называются {{не переведено 5|Полутранзитивный граф|полутранзитивными||half-transitive graph}}.<ref name="handbook">{{книга
| автор =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
| страницы =491
| год =2004
| страницы =491
| isbn =1-58488-090-2
| isbn =1-58488-090-2}}</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
| том =5
| выпуск =2
| том =5
| выпуск =2
| страницы =201–204
| страницы =201—204
| год =1981
⚫
| год =1981
⚫
| doi =10.1002/jgt.3190050210}}.</ref> Запутывает то, что некоторые авторы используют термин "симметричный граф" для графов, которые одновременно являются вершинно-транзитивными и рёберно-транзитивными. Такое определение включает полутранзитивные графы, которые исключены определением выше.
| doi =10.1002/jgt.3190050210
⚫
}}.</ref> Запутывает то, что некоторые авторы используют термин «симметричный граф» для графов, которые одновременно являются вершинно-транзитивными и рёберно-транзитивными. Такое определение включает полутранзитивные графы, которые исключены определением выше.


[[Дистанционно-транзитивный граф]] — это граф, в котором вместо единичного расстояния смежные вершины находятся на одном и том же фиксированном расстоянии. Такие графы по определению симметричны.<ref name="biggs" />
[[Дистанционно-транзитивный граф]] — это граф, в котором вместо единичного расстояния смежные вершины находятся на одном и том же фиксированном расстоянии. Такие графы по определению симметричны.<ref name="biggs" />


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


== Примеры ==
== Примеры ==
Сочетание условий симметрии с условием, что граф {{не переведено 5|Кубическй граф|кубический||Cubic graph|cubic}} (т.е. все вершины имеют степень 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-х годах {{не переведено 5|Фостер, Рональд Мартин|Р.М. Фостером||R. M. Foster}} во время его работы в [[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> (десять из них — [[Дистанционно-транзитивный граф|дистанционно-транзитивные]]),
приведены ниже в таблице
приведены ниже в таблице
{{якорь|Список Фостера}}

{| class="wikitable"
{| class="wikitable"
|-
|-
Строка 68: Строка 78:
|6 || 2 || 4 || [[полный двудольный граф]] ''K''<sub>3,3</sub> || дистанционно транзитивен, 3-транзитивен
|6 || 2 || 4 || [[полный двудольный граф]] ''K''<sub>3,3</sub> || дистанционно транзитивен, 3-транзитивен
|-
|-
|8 || 3 || 4 || вершины и рёбра [[Куб|куба]] || дистанционно транзитивен, 2-транзитивен
|8 || 3 || 4 || вершины и рёбра [[куб]]а || дистанционно транзитивен, 2-транзитивен
|-
|-
|10 || 2 || 5 || [[граф Петерсена]] || дистанционно транзитивен, 3-транзитивен
|10 || 2 || 5 || [[граф Петерсена]] || дистанционно транзитивен, 3-транзитивен
|-
|-
|14 || 3 || 6 || [[граф Хивуда]] || дистанционно транзитивен, 4-транзитивен
|14 || 3 || 6 || [[граф Хивуда]] || дистанционно транзитивен, 4-транзитивен
|-
|-
|16 || 4 || 6 || [[Граф Мёбиуса–Кантора|граф Мёбиуса–Кантора]] || 2-транзитивен
|16 || 4 || 6 || [[граф Мёбиуса — Кантора]] || 2-транзитивен
|-
|-
|18 || 4 || 6 || [[Граф Паппа|граф Паппа]] || дистанционно транзитивен, 3-транзитивен
|18 || 4 || 6 || [[граф Паппа]] || дистанционно транзитивен, 3-транзитивен
|-
|-
|20 || 5 || 5 || вершины и рёбра [[Додекаэдр|додекаэдра]] || дистанционно транзитивен, 2-транзитивен
|20 || 5 || 5 || вершины и рёбра [[додекаэдр]]а || дистанционно транзитивен, 2-транзитивен
|-
|-
|20 || 5 || 6 || [[Граф Дезарга|граф Дезарга]] || дистанционно транзитивен, 3-транзитивен
|20 || 5 || 6 || [[граф Дезарга]] || дистанционно транзитивен, 3-транзитивен
|-
|-
|24 || 4 || 6 || {{не переведено 5|Граф Науру|граф Науру||Nauru graph}} ({{не переведено 5|Обобщённый граф Петерсена |обобщённый граф Петерсена||generalized Petersen graph}} G(12,5)) || 2-транзитивен
|24 || 4 || 6 || [[граф Науру]] ([[обобщённый граф Петерсена]] G(12,5)) || 2-транзитивен
|-
|-
|26 || 5 || 6 || {{не переведено 5|Граф F26A|граф F26A||F26A graph}}<ref name="F26A"/> || 1-транзитивен
|26 || 5 || 6 || [[граф F26A]]<ref name="F26A"/> || 1-транзитивен
|-
|-
|28 || 4 || 7 || {{не переведено 5|Граф Коксетера|граф Коксетера||Coxeter graph}} || дистанционно транзитивен, 3-транзитивен
|28 || 4 || 7 || [[граф Коксетера]] || дистанционно транзитивен, 3-транзитивен
|-
|-
|30 || 4 || 8 || [[Граф Тутте-Коксетера|граф Тутте-Коксетера]] || дистанционно транзитивен, 5-транзитивен
|30 || 4 || 8 || [[граф Татта — Коксетера]] || дистанционно транзитивен, 5-транзитивен
|}
|}


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


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


== Свойства ==
== Свойства ==
[[Связный граф|Вершинная связность]] симметричного графа всегда равна [[Регулярный граф|степени]] ''d''.<ref name="babai" /> Для контраста, для общих [[Вершинно-транзитивный граф|вершинно-транзитивных графов]] вершинная связность ограничена снизу числом 2(''d''+1)/3.<ref name="godsil" />
[[Связный граф|Вершинная связность]] симметричного графа всегда равна [[Регулярный граф|степени]] ''d''.<ref name="babai" /> Для контраста, для общих [[Вершинно-транзитивный граф|вершинно-транзитивных графов]] вершинная связность ограничена снизу числом 2(''d''+1)/3.<ref name="godsil" />


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


== Смотрите также ==
== См. также ==
* {{не переведено 5|Алгебраическая теория графов|Алгебраическая теория графов||Algebraic graph theory}}
* [[Алгебраическая теория графов]]
* {{не переведено 5|Галерея именованных графов#Симметричные графы|Галерея именованных графов||Gallery of named graphs#Symmetric graphs}}
* {{не переведено 5|Галерея именованных графов|Галерея именованных графов|en|Gallery of named graphs}}
* [[Правильная карта (теория графов)|Правильная карта]]
* {{не переведено 5|Регулярное отображение (теория графов)|Регулярное отображение||Regular map (graph theory)}}


== Примечания ==
== Примечания ==
{{примечания}}
{{примечания}}


== Ссылки ==
== Внешние ссылки ==
* [http://people.csse.uwa.edu.au/gordon/remote/foster/ 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.
* [https://web.archive.org/web/20081004205049/http://people.csse.uwa.edu.au/gordon/remote/foster/ 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.
* [http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt Trivalent (cubic) symmetric graphs on up to 2048 vertices]. [[Marston Conder]], August 2006, retrieved 2009-08-20.
* [http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt Trivalent (cubic) symmetric graphs on up to 2048 vertices]. [[Marston Conder]], August 2006, retrieved 2009-08-20.


{{rq|checktranslate|style|grammar}}
{{rq|cleanup<!--формулы-->|checktranslate|style}}


[[Категория:Теория графов]]
[[Категория:Алгебраическая теория графов]]
[[Категория:Семейства графов]]
[[Категория:Регулярные графы]]

Текущая версия от 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. ↑ 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. Архивировано 11 июня 2010 года.
  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 Архивная копия от 15 июня 2011 на Wayback Machine, 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 Архивная копия от 5 января 2011 на Wayback Machine», from Wolfram MathWorld.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Симметричный_граф&oldid=135080014