Симметричный граф - Symmetric graph
в математический поле теория графов, а график г является симметричный (или дуговой переходный), если для любых двух пар смежных вершин ты1—v1 и ты2—v2 из г, существует автоморфизм
- ж : V(г) → V(г)
такой, что
- ж(ты1) = ты2 и ж(v1) = v2.[1]
Другими словами, граф является симметричным, если его группа автоморфизмов действует переходно на упорядоченных парах смежных вершин (то есть на ребрах, считающихся имеющими направление).[2] Такой граф иногда также называют 1-дуговая транзитивная[2] или флаг транзитивный.[3]
По определению (игнорируя ты1 и ты2) симметричный граф без изолированные вершины также должен быть вершинно-транзитивный.[1] Поскольку приведенное выше определение отображает одно ребро в другое, симметричный граф также должен быть реберно-транзитивный. Однако реберно-транзитивный граф не обязательно должен быть симметричным, поскольку а—б может соответствовать c—d, но не d—c. Звездные графики являются простым примером транзитивности по ребрам без транзитивности по вершинам или симметрии. В качестве дополнительного примера, полусимметричные графы реберно-транзитивны и регулярный, но не вершинно-транзитивный.
Каждые связанный симметричный граф, таким образом, должен быть как вершинно-транзитивным, так и реберно-транзитивным, и обратное верно для графов странный степень.[3] Однако для даже степени, существуют связные графы, которые транзитивны по вершинам и реберно, но не симметричны.[4] Такие графы называются полупереходный.[5] Наименьший связный полупереходный граф - это График Холта, со степенью 4 и 27 вершинами.[1][6] Что сбивает с толку, некоторые авторы используют термин «симметричный граф» для обозначения графа, который является вершинно-транзитивным и реберно-транзитивным, а не дуго-транзитивным графом. Такое определение будет включать полутранзитивные графы, которые исключены согласно определению выше.
А дистанционно-транзитивный граф - это такое, в котором вместо рассмотрения пар соседних вершин (то есть вершин на расстоянии 1 друг от друга) определение охватывает две пары вершин, каждая на одинаковом расстоянии друг от друга. Такие графы автоматически симметричны по определению.[1]
А т-arc определяется как последовательность из т +1 вершина, такие, что любые две последовательные вершины в последовательности смежны, а любые повторяющиеся вершины находятся на расстоянии более 2 шагов друг от друга. А т-переходный граф - граф такой, что группа автоморфизмов действует транзитивно на т-дуги, но не на (т + 1) -дуги. Поскольку 1-дуги - это просто ребра, каждый симметричный граф степени 3 или выше должен быть т-транзитивен для некоторых т, а значение т может использоваться для дальнейшей классификации симметричных графов. Куб, например, 2-транзитивен.[1]
Примеры
Комбинируя условие симметрии с ограничением, что графы кубический (т.е. все вершины имеют степень 3) дает довольно сильное условие, и такие графы достаточно редки, чтобы их можно было перечислить. В Приемная перепись и его расширения предоставляют такие списки.[7] Перепись Фостера была начата в 1930-х гг. Рональд М. Фостер в то время как он был нанят Bell Labs,[8] а в 1988 году (когда Фостеру было 92[1]текущая на тот момент перепись населения Фостера (перечисляющая все кубические симметричные графы до 512 вершин) была опубликована в виде книги.[9] Первые тринадцать элементов в списке - это кубические симметричные графы с числом вершин до 30.[10][11] (десять из них также дистанционно-переходный; указаны исключения):
| Вершины | Диаметр | Обхват | График | Заметки |
|---|---|---|---|---|
| 4 | 1 | 3 | В полный график K4 | дистанционно-переходная, 2-дуговая переходная |
| 6 | 2 | 4 | В полный двудольный граф K3,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 или более вершин), а графы, образованные вершинами и ребрами октаэдр, икосаэдр, кубооктаэдр, и икосододекаэдр. В График Rado образует пример симметричного графа с бесконечным числом вершин и бесконечной степенью.
Свойства
В вершинная связность симметричного графа всегда равна степень d.[3] Напротив, для вершинно-транзитивные графы в общем случае связность вершин ограничена снизу 2 (d + 1)/3.[2]
А т-транзитивный граф степени 3 и выше имеет обхват не менее 2 (т - 1). Однако конечных т-транзитивные графы степени 3 и выше длят ≥ 8. В случае ровно 3 степени (кубические симметричные графы) их нет длят ≥ 6.
Смотрите также
использованная литература
- ^ а б c d е ж Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. С. 118–140. ISBN 0-521-45897-8.
- ^ а б c Годсил, Крис; Ройл, Гордон (2001). Алгебраическая теория графов. Нью-Йорк: Спрингер. п.59. ISBN 0-387-95220-9.
- ^ а б c Бабай, Л. (1996). «Группы автоморфизмов, изоморфизм, реконструкция». В Graham, R; Грётшель, М; Ловас, Л. (ред.). Справочник по комбинаторике. Эльзевир.
- ^ Бауэр, З. «Вершинные и реберные транзитивные, но не 1-транзитивные графы». Канад. Математика. Бык. 13, 231–237, 1970.
- ^ Гросс, Дж. Л. и Йеллен, Дж. (2004). Справочник по теории графов. CRC Press. п. 491. ISBN 1-58488-090-2.
- ^ Холт, Дерек Ф. (1981). «Граф, который транзитивен по ребрам, но не транзитивен по дуге». Журнал теории графов. 5 (2): 201–204. Дои:10.1002 / jgt.3190050210..
- ^ Марстон Кондер, Трехвалентные симметричные графы с числом вершин до 768, J. Combin. Математика. Комбинировать. Вычислить, т. 20. С. 41–63.
- ^ Фостер, Р. М. "Геометрические схемы электрических сетей". Труды Американского института инженеров-электриков 51, 309–317, 1932.
- ^ «Перепись Фостера: перепись связных симметричных трехвалентных графов Р.М. Фостера», Рональд М. Фостер, И.З. Бауэр, W.W. Чернов, Б. Монсон и З. Стар (1988) ISBN 0-919611-19-2
- ^ Биггс, стр. 148
- ^ а б Вайсштейн, Эрик В. "Кубический симметричный граф ", из Wolfram MathWorld.
внешние ссылки
- Кубические симметричные графы (перепись Фостера). Файлы данных для всех кубических симметричных графов с числом вершин до 768 и некоторых кубических графов с числом вершин до 1000. Гордон Ройл, обновлено в феврале 2001 г., получено 18 апреля 2009 г.
- Трехвалентные (кубические) симметричные графы с числом вершин до 2048. Марстон Кондер, Август 2006 г., получено 20 августа 2009 г.