![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/langru-640px-Petersen1_tiny.svg.png&w=640&q=50)
Симметричный граф
раф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Симметричный граф?
Кратко изложите эту статью для 10-летнего ребёнка
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм:
- f : V(G) → V(G)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/200px-Petersen1_tiny.svg.png)
такой, что:
- 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]