В математической области теории графов , А граф G является симметричным (или дуги транзитивным ) , если для любых двух пар смежных вершин ¯u 1 - v 1 и U 2 - v 2 из G , существует автоморфизм
- е : V ( G ) → V ( G )
такой, что
- f ( u 1 ) = u 2 и f ( v 1 ) = v 2 . [1]
Другими словами, граф является симметричным, если его группа автоморфизмов транзитивно действует на упорядоченные пары смежных вершин (то есть на ребра, рассматриваемые как имеющие направление). [2] Такой граф иногда также называют 1-арк-транзитивным [2] или флаг-транзитивным . [3]
По определению ( без учета u 1 и u 2 ) симметричный граф без изолированных вершин также должен быть вершинно-транзитивным . [1] Поскольку в приведенном выше определении одно ребро отображается в другое, симметричный граф также должен быть реберно-транзитивным . Однако реберно-транзитивный граф не обязательно должен быть симметричным, поскольку a - b может отображаться в c - d , но не в d - c . Звездные графы - простой пример того, что они транзитивны по ребрам, но не являются вершинно-транзитивными или симметричными. В качестве еще одного примера полусимметричные графыреберно-транзитивны и регулярны , но не вершинно-транзитивны.
Таким образом, каждый связный симметричный граф должен быть одновременно вершинно-транзитивным и реберно-транзитивным, и обратное верно для графов нечетной степени. [3] Однако для четной степени существуют связные графы, которые транзитивны по вершинам и транзитивны по ребрам, но не симметричны. [4] Такие графы называются полупереходными . [5] Наименьший связный полутранзитивный граф - это граф Холта со степенью 4 и 27 вершинами. [1] [6]Что сбивает с толку, некоторые авторы используют термин «симметричный граф» для обозначения графа, который является вершинно-транзитивным и реберно-транзитивным, а не дуго-транзитивным графом. Такое определение будет включать полутранзитивные графы, которые исключены в соответствии с определением выше.
Расстояние-симметрический граф один , где вместо того , чтобы рассматривать пар смежных вершин (т.е. вершин на расстоянии друг от друга 1), крышки определения две пары вершин, каждая из которых на одинаковом расстоянии друг от друга. Такие графы автоматически симметричны по определению. [1]
Т -arc определена , чтобы быть последовательность из т + 1 вершин, таких , что любые две последовательные вершины в последовательности являются смежными, а также с любыми повторяющиеся вершины быть больше , чем 2 шага друг от друга. Т -транзитивной график представляет собой график таким образом, что группа автоморфизмов действует транзитивно на т -arcs, но не на ( т + 1) -arcs. Поскольку 1-дуги - это просто ребра, каждый симметричный граф степени 3 или выше должен быть t -транзитивным для некоторого t , а значение t может использоваться для дальнейшей классификации симметричных графов. Куб, например, 2-транзитивен. [1]
Примеры [ править ]
Комбинация условия симметрии с ограничением, что графы должны быть кубическими (т.е. все вершины имеют степень 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-дуговая переходная |
Другие хорошо известные кубических симметричные графы являются граф Дейк , то график Фостер и график Биггс-Смита . Десять расстояние-транзитивные графы , перечисленные выше, вместе с графом Фостер и графа Биггс-Смита , являются только кубическая расстояние-транзитивные графы.
Некубические симметричные графы включают циклические графы (степени 2), полные графы (степени 4 или более, когда имеется 5 или более вершин), графы гиперкуба (степени 4 или более, когда имеется 16 или более вершин) и графы, образованные вершинами и ребрами октаэдра , икосаэдра , кубооктаэдра и икосододекаэдра . Граф Радо представляет собой пример симметричного графа с бесконечным числом вершин и бесконечной степенью.
Свойства [ править ]
Вершина-подключение симметричного графа всегда равна степени д . [3] В отличие от этого, для вершинно-транзитивных графов в целом связность вершин ограничена снизу величиной 2 ( d + 1) / 3. [2]
Т -транзитивный граф степени 3 или более имеет обхват по крайней мере , 2 ( т - 1). Однако не существует конечных t -транзитивных графов степени 3 и выше для t ≥ 8. В случае, когда степень равна точно 3 (кубические симметричные графы), их нет при t ≥ 6.
См. Также [ править ]
- Алгебраическая теория графов
- Галерея именованных графов
- Обычная карта
Ссылки [ править ]
- ^ Б с д е е Биггсом, Norman (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. С. 118–140. ISBN 0-521-45897-8.
- ^ a b c Годсил, Крис ; Ройл, Гордон (2001). Алгебраическая теория графов . Нью-Йорк: Спрингер. п. 59 . ISBN 0-387-95220-9. CS1 maint: discouraged parameter (link)
- ^ a b c Бабай, L (1996). «Группы автоморфизмов, изоморфизм, реконструкция» . В Graham, R; Grötschel, M ; Ловас, Л. (ред.). Справочник по комбинаторике . Эльзевир.
- ^ Бауэр, З. «Вершинные и реберные транзитивные, но не 1-транзитивные графы». Канад. Математика. Бык. 13, 231–237, 1970.
- Перейти ↑ Gross, JL & Yellen, J. (2004). Справочник по теории графов . CRC Press. п. 491. ISBN. 1-58488-090-2.
- ^ Холт, Дерек Ф. (1981). «Граф, который является реберно транзитивным, но не дугообразным». Журнал теории графов . 5 (2): 201–204. DOI : 10.1002 / jgt.3190050210 ..
- ^ Марстон Кондер , Трехвалентные симметричные графы с числом вершин до 768 , J. Combin. Математика. Комбинировать. Вычислить, т. 20. С. 41–63.
- ^ Фостер, Р.М. "Геометрические схемы электрических сетей". Труды Американского института инженеров-электриков 51 , 309–317, 1932.
- ^ "Перепись Фостера: Перепись Р. М. Фостера связанных симметричных трехвалентных графов", Рональд М. Фостер, И. З. Бауэр, В. В. Чернофф, Б. Монсон и З. Стар (1988) ISBN 0-919611-19-2
- ^ Биггс, стр. 148
- ^ a b Вайсштейн, Эрик В., « Кубический симметричный граф », из Wolfram MathWorld.
Внешние ссылки [ править ]
- Кубические симметричные графы (перепись Фостера) . Файлы данных для всех кубических симметричных графов с числом вершин до 768 и некоторых кубических графов с числом вершин до 1000. Гордон Ройл, обновлено в феврале 2001 г., получено 18 апреля 2009 г.
- Трехвалентные (кубические) симметричные графы с числом вершин до 2048 . Marston Conder , август 2006 г., получено 20 августа 2009 г.
