Симметричный граф
В математической области теории графов граф G ) , является симметричным (или дуготранзитивным если для любых двух пар смежных вершин u 1 — v 1 и u 2 — v 2 графа G существует автоморфизм
такой, что
- и [1]
Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах соседних вершин (то есть на ребрах, которые считаются имеющими направление). [2] Такой граф иногда еще называют 1-дуговым -транзитивным. [2] или транзитивный по флагу . [3]
По определению (игнорируя и также u2 ) u1 , симметричный граф без изолированных вершин должен быть вершинно-транзитивным . [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 измерений дает графы перекрестных многогранников . Это семейство графов (с 2n вершинами и степенью 2n-2) иногда называют графами для коктейльных вечеринок — они представляют собой полные графы с набором ребер. создание идеального соответствия удалено. Дополнительными семействами симметричных графов с четным числом вершин 2n являются равномерно разделенные полные двудольные графы K n,n и графы-короны на 2n вершинах. Многие другие симметричные графы можно отнести к циркулянтным графам (но не все).
Граф Радо представляет собой пример симметричного графа с бесконечным числом вершин и бесконечной степенью.
Кубические симметричные графы
[ редактировать ]Сочетание условия симметрии с ограничением на кубичность графов (т. е. все вершины имеют степень 3) дает довольно сильное условие, и такие графы достаточно редки, чтобы их можно было перечислить. Все они имеют четное количество вершин. Перепись Фостера и ее дополнения предоставляют такие списки. [7] Перепись Фостера была начата в 1930-х годах Рональдом М. Фостером, когда он работал в Bell Labs . [8] а в 1988 году (когда Фостеру было 92 года) [1] ) текущая на тот момент перепись Фостера (с перечислением всех кубических симметричных графов до 512 вершин) была опубликована в виде книги. [9] Первые тринадцать элементов списка представляют собой кубически-симметричные графы с числом вершин до 30. [10] [11] (десять из них также являются дистанционно-транзитивными ; исключения указаны так:
| Вершины | Диаметр | Обхват | График | Примечания |
|---|---|---|---|---|
| 4 | 1 | 3 | Полный граф K 4 | дистанционно-переходной, 2-дуговой переходный |
| 6 | 2 | 4 | Полный двудольный граф K 3,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-дуговой переходный |
Другими хорошо известными кубическими симметричными графами являются граф Дика , граф Фостера и граф Биггса-Смита . Перечисленные выше десять дистанционно-транзитивных графов вместе с графом Фостера и графом Биггса-Смита являются единственными кубическими дистанционно-транзитивными графами.
Характеристики
[ редактировать ]Вершинная связность симметричного графа всегда равна степени d . [3] Напротив, для вершинно-транзитивных графов в целом связность вершин ограничена снизу величиной 2( d + 1)/3. [2]
-транзитивный граф t степени 3 и выше имеет обхват не менее 2( t – 1). Однако не существует конечных t -транзитивных графов степени 3 или более для t ≥ 8. В случае, когда степень равна ровно 3 (кубические симметричные графы), их нет для t ≥ 6.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с д и ж Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. стр. 118–140. ISBN 0-521-45897-8 .
- ↑ Перейти обратно: Перейти обратно: а б с Годсил, Крис ; Ройл, Гордон (2001). Алгебраическая теория графов . Нью-Йорк: Спрингер. п. 59 . ISBN 0-387-95220-9 .
- ↑ Перейти обратно: Перейти обратно: а б с Бабай, Л (1996). «Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . В Грэме, Р.; Гретшель, М ; Ловас, Л. (ред.). Справочник по комбинаторике . Эльзевир.
- ^ Бауэр, З. (1970). «Вершинные и реберные транзитивные, но не 1-транзитивные графы» . Канада. Математика. Бык. 13 : 231–237. дои : 10.4153/CMB-1970-047-8 .
- ^ Гросс, Дж. Л. и Йеллен, Дж. (2004). Справочник по теории графов . ЦРК Пресс. п. 491. ИСБН 1-58488-090-2 .
- ^ Холт, Дерек Ф. (1981). «Граф, транзитивный по ребрам, но не транзитивный по дугам». Журнал теории графов . 5 (2): 201–204. дои : 10.1002/jgt.3190050210 . .
- ^ Марстон Кондер , Трехвалентные симметричные графы с числом вершин до 768 , Дж. Комбин. Математика. Комбинировать. Компьютер, том. 20, стр. 41–63.
- ^ Фостер, Р.М. «Геометрические схемы электрических сетей». Труды Американского института инженеров-электриков 51 , 309–317, 1932.
- ^ «Перепись Фостера: перепись Р. М. Фостера связанных симметричных трехвалентных графов», Рональд М. Фостер, И. З. Бауэр, В. В. Чернофф, Б. Монсон и З. Стар (1988) ISBN 0-919611-19-2
- ^ Биггс, с. 148
- ↑ Перейти обратно: Перейти обратно: а б Вайсштейн, Эрик В., « Кубический симметричный граф », из Wolfram MathWorld.
Внешние ссылки
[ редактировать ]- Кубические симметричные графы (Перепись Фостера) . Файлы данных для всех кубических симметричных графов до 768 вершин и некоторых кубических графов до 1000 вершин. Гордон Ройл, обновлено в феврале 2001 г., получено 18 апреля 2009 г.
- Трехвалентные (кубические) симметричные графы с числом вершин до 10000 . Марстон Кондер , 2011.