В математической области теории графов граф G является симметричным (или дуготранзитивным ), если для любых двух пар смежных вершин u 1 — v 1 и u 2 — v 2 графа G существует автоморфизм
такой, что
Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин (то есть на ребрах, которые считаются имеющими направление). [2] Такой граф иногда также называют 1-дуго -транзитивным [2] или флаг-транзитивным . [3]
По определению (игнорируя u1 и u2 ) , симметричный граф без изолированных вершин также должен быть вершинно-транзитивным . [1] Поскольку приведенное выше определение отображает одно ребро в другое, симметричный граф также должен быть транзитивным по ребрам . Однако реберно-транзитивный граф не обязательно должен быть симметричным, поскольку a-b может отображаться в c-d , но не в d-c . Звездчатые графы являются простым примером того, что они транзитивны по ребрам, но не являются транзитивными по вершинам или симметричными. Еще один пример: полусимметричные графы транзитивны по ребрам и регулярны , но не транзитивны по вершинам.
Таким образом, каждый связный симметричный граф должен быть как вершинно-транзитивным, так и реберно-транзитивным, и обратное верно для графов нечетной степени . [3] Однако для четной степени существуют связные графы, которые являются вершинно-транзитивными и реберно-транзитивными, но не симметричными. [4] Такие графы называются полутранзитивными . [5] Наименьшим связным полутранзитивным графом является граф Холта со степенью 4 и 27 вершинами. [1] [6] Как ни странно, некоторые авторы используют термин «симметричный граф» для обозначения графа, который является транзитивным по вершинам и ребрам, а не к транзитивным по дугам графам. Такое определение будет включать полутранзитивные графы, которые исключены из определения выше.
Дистанционно -транзитивный граф — это граф, в котором вместо рассмотрения пар соседних вершин (т. е. вершин, находящихся на расстоянии 1 друг от друга), определение охватывает две пары вершин, каждая из которых находится на одинаковом расстоянии друг от друга. Такие графы автоматически симметричны по определению. [1]
T -дуга определяется как последовательность из t + 1 вершины, в которой любые две последовательные вершины в последовательности являются смежными, а любые повторяющиеся вершины находятся на расстоянии более 2 шагов друг от друга. t - транзитивный граф — это граф, в котором группа автоморфизмов действует транзитивно на t -дугах , но не на ( t +1 )-дугах . Поскольку 1-дуги — это просто ребра, каждый симметричный граф степени 3 или более должен быть t -транзитивным для некоторого t , и значение t можно использовать для дальнейшей классификации симметричных графов. Например, куб 2-транзитивен . [1]
Обратите внимание, что традиционно термин «симметричный граф» не дополняет термин « асимметричный граф », поскольку последний относится к графу, который вообще не имеет нетривиальных симметрий.
Двумя основными семействами симметричных графов для любого числа вершин являются графы циклов (степени 2) и полные графы . Далее симметричные графы образуются вершинами и рёбрами правильных и квазиправильных многогранников: куба , октаэдра , икосаэдра , додекаэдра , кубооктаэдра и икосододекаэдра . Расширение куба до n измерений дает графы гиперкуба (с 2 n вершинами и степенью n). Аналогичным образом расширение октаэдра до n измерений дает графы перекрестных многогранников . Это семейство графов (с 2n вершинами и степенью 2n-2) иногда называют графами для коктейльных вечеринок — они представляют собой полные графы с набором ребер. создание идеального соответствия удалено. Дополнительными семействами симметричных графов с четным числом вершин 2n являются равномерно разделенные полные двудольные графы K n,n и графы-короны на 2n вершинах. Многие другие симметричные графы можно отнести к циркулянтным графам (но не все).
Граф Радо представляет собой пример симметричного графа с бесконечным числом вершин и бесконечной степенью.
Сочетание условия симметрии с ограничением на кубичность графов (т. е. все вершины имеют степень 3) дает довольно сильное условие, и такие графы достаточно редки, чтобы их можно было перечислить. Все они имеют четное количество вершин. Перепись Фостера и ее дополнения предоставляют такие списки. [7] Перепись Фостера была начата в 1930-х годах Рональдом М. Фостером, когда он работал в Bell Labs , [8] и в 1988 году (когда Фостеру было 92 года [1] ) текущая на тот момент перепись Фостера (с перечислением всех кубических симметричных графов). до 512 вершин) был издан в виде книги. [9] Первые тринадцать элементов в списке представляют собой кубически-симметричные графы с числом вершин до 30 [10] [11] (десять из них также являются дистанционно-транзитивными ; исключения указаны так):
Другими хорошо известными кубическими симметричными графами являются граф Дика , граф Фостера и граф Биггса-Смита . Перечисленные выше десять дистанционно-транзитивных графов вместе с графом Фостера и графом Биггса-Смита являются единственными кубическими дистанционно-транзитивными графами.
Вершинная связность симметричного графа всегда равна степени d . [3] Напротив, для вершинно-транзитивных графов в целом связность вершин ограничена снизу величиной 2( d + 1)/3. [2]
t -транзитивный граф степени 3 и выше имеет обхват не менее 2( t – 1). Однако не существует конечных t -транзитивных графов степени 3 или более для t ≥ 8. В случае, когда степень равна ровно 3 (кубические симметричные графы), их нет для t ≥ 6.
