В математической области теории графов граф G называется симметричным (или реберно-транзитивным ) , если для любых двух пар смежных вершин u1 — v1 и u2 — v2 графа G существует автоморфизм
такой что
Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин (то есть на ребрах, рассматриваемых как имеющие направление). [2] Такой граф иногда также называют 1-дуго -транзитивным [2] или флаг-транзитивным . [3]
По определению (игнорируя u 1 и u 2 ), симметричный граф без изолированных вершин также должен быть вершинно-транзитивным . [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 измерений дает графы гиперкуба (с 2n вершинами и степенью 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 их нет .
