Странный график

Странный график
Странный график
	это график Петерсена
Вершины
Края
Диаметр
Обхват	3 для ; 5 за ; 6 иначе
Характеристики	Дистанционно-транзитивный
Обозначения	На
	Таблица графиков и параметров

В математической области теории графов нечетные графы представляют собой семейство симметричных графов, определенных на основе определенных систем множеств . Они включают и обобщают граф Петерсена .

Нечетные графы имеют большой нечетный обхват , что означает, что они содержат длинные циклы нечетной длины, но не содержат коротких. Однако их название происходит не от этого свойства, а от того факта, что каждое ребро графа имеет «лишнего человечка», элемент, который не участвует в двух множествах, соединенных ребром.

Определение и примеры

Странный график $O_{n}$ имеет по одной вершине для каждого из $(n-1)$ -элементные подмножества $(2n-1)$ - набор элементов. Две вершины соединены ребром тогда и только тогда, когда соответствующие подмножества не пересекаются . ^[2] То есть, $O_{n}$ это граф Кнезера $KG(2n-1,n-1)$ .

$O_{2}$ представляет собой треугольник, а $O_{3}$ – это знакомый граф Петерсена .

Обобщенные нечетные графы определяются как дистанционно регулярные графы с диаметром $n-1$ и странный обхват $2n-1$ для некоторых $n$ . ^[4] К ним относятся нечетные графы и графы свернутых кубов .

История и приложения

Хотя граф Петерсена известен с 1898 года, его определение как нечетного графа восходит к работе Ковалевского (1917) , который также изучал нечетный граф. $O_{4}$ . ^[2]^[5]Нечетные графы изучались для их применения в химической теории графов , при моделировании сдвигов ионов карбония . ^[6]^[7] Они также были предложены в качестве топологии сети в параллельных вычислениях . ^[8]

Обозначения $O_{n}$ для этих графиков был введен Норманом Биггсом в 1972 году. ^[9] Биггс и Тони Гардинер объясняют название нечетных графов в неопубликованной рукописи 1974 года: каждому ребру нечетного графа можно присвоить уникальный элемент, который является « лишним », т. е. не является членом ни одного из подмножеств, связанных с вершинами. инцидентный этому краю. ^[10]^[11]

Характеристики

Странный график $O_{n}$ регулярен степени $n$ . Он имеет ${\tbinom {2n-1}{n-1}}$ вершины и $n{\tbinom {2n-1}{n-1}}/2$ края. Следовательно, количество вершин для $n=1,2,\dots$ является

1, 3, 10, 35, 126, 462, 1716, 6435 (последовательность A001700 в OEIS ).

Расстояние и симметрия

Если две вершины в $O_{n}$ соответствуют множествам, отличающимся друг от друга удалением $k$ элементы из одного набора и добавление $k$ разные элементы, то они могут быть достигнуты друг от друга в $2k$ шаги, каждая пара которых выполняет одно добавление и удаление. Если $2k<n$ , это кратчайший путь ; в противном случае проще найти путь этого типа от первого набора к множеству, дополнительному ко второму, а затем достичь второго набора еще за один шаг. , диаметр Следовательно $O_{n}$ является $n-1$ . ^[1]^[2]

Каждый нечетный граф является транзитивным по 3 дугам : каждый направленный путь с тремя ребрами в нечетном графе может быть преобразован в любой другой такой путь за счет симметрии графа. ^[12]Нечетные графы дистанционно транзитивны , следовательно, дистанционно регулярны . ^[2] Как дистанционно регулярные графы, они однозначно определяются своим массивом пересечений: никакие другие дистанционно регулярные графы не могут иметь те же параметры, что и нечетный граф. ^[13] Однако, несмотря на высокую степень симметрии, странные графы $O_{n}$ для $n>2$ никогда не являются графами Кэли . ^[14]

Поскольку нечетные графы регулярны и транзитивны по ребрам их , связность вершин равна их степени, $n$ . ^[15]

Странные графики с $n>3$ иметь обхват шесть; однако, хотя они и не являются двудольными графами , их нечетные циклы гораздо длиннее. В частности, нечетный график $O_{n}$ имеет странный обхват $2n-1$ . Если $n$ -регулярный граф имеет диаметр $n-1$ и странный обхват $2n-1$ , и имеет только $n$ различные собственные значения , оно должно быть дистанционно регулярным. Дистанционно-регулярные графы с диаметром $n-1$ и странный обхват $2n-1$ известны как обобщенные нечетные графы и включают в себя графы свернутых кубов, а также сами нечетные графы. ^[4]

Независимые множества и раскраска вершин

Позволять $O_{n}$ быть нечетным графом, определенным из подмножеств a $(2n-1)$ - набор элементов $X$ , и пусть $x$ быть любым членом $X$ . Тогда среди вершин $O_{n}$ , точно ${\tbinom {2n-2}{n-2}}$ вершины соответствуют множествам, содержащим $x$ . Поскольку все эти наборы содержат $x$ , они не не пересекаются и образуют независимый набор $O_{n}$ . То есть, $O_{n}$ имеет $2n-1$ разные независимые наборы размеров ${\tbinom {2n-2}{n-2}}$ . следует Из теоремы Эрдеша–Ко–Радо , что это максимальные независимые множества $O_{n}$ . то есть независимости число $O_{n}$ является ${\tbinom {2n-2}{n-2}}.$ Далее, каждое максимально независимое множество должно иметь такой вид, поэтому $O_{n}$ имеет точно $2n-1$ максимально независимые множества. ^[2]

Если $I$ — максимальное независимое множество, образованное множествами, содержащими $x$ , дополнение то $I$ множество вершин, не содержащих $x$ . дополнительный набор индуцирует паросочетание в Этот $G$ . Каждая вершина независимого множества смежна с $n$ вершины паросочетания, причем каждая вершина паросочетания смежна с $n-1$ вершины независимого множества. ^[2] Из-за этого разложения, а также из-за того, что нечетные графы не являются двудольными, они имеют хроматическое число три: вершинам максимального независимого множества можно присвоить один цвет, а еще двух цветов достаточно, чтобы раскрасить дополнительное паросочетание.

Краевая окраска

По теореме Визинга количество цветов, необходимых для раскраски ребер нечетного графа $O_{n}$ либо $n$ или $n+1$ , а в случае графа Петерсена $O_{3}$ это $n+1$ . Когда $n$ является степенью двойки, число вершин в графе нечетное, откуда снова следует, что количество цветов ребер равно $n+1$ . ^[16] Однако, $O_{5}$ , $O_{6}$ , и $O_{7}$ каждый может быть окрашен в цвет края с помощью $n$ цвета. ^[2]^[16]

Биггс ^[9] объясняет эту проблему следующей историей: одиннадцать футболистов в вымышленном городе Кроам хотят сформировать пары команд по пять человек (с лишним человеком, который будет выступать в качестве судьи) всеми 1386 возможными способами, и они хотят запланировать игры между каждой парой таким образом, чтобы шесть игр для каждой команды проводились в шесть разных дней недели, с выходными для всех команд по воскресеньям. Возможно ли это сделать? В этой истории каждая игра представляет собой грань $O_{6}$ , каждый день недели представлен своим цветом, а 6-цветная окраска краев $O_{6}$ обеспечивает решение проблемы планирования игроков.

гамильтоновость

График Петерсена $O_{3}$ — хорошо известный негамильтонов граф, но все нечетные графы $O_{n}$ для $n\geq 4$ известно, что они имеют гамильтонов цикл. ^[17]Поскольку нечетные графы вершинно-транзитивны , они, таким образом, являются одним из частных случаев с известным положительным ответом на гипотезу Ловаса о гамильтоновых циклах в вершинно-транзитивных графах. Биггс ^[2] в более общем плане предположил, что края $O_{n}$ можно разделить на $\lfloor n/2\rfloor$ реберно-непересекающиеся гамильтоновы циклы. Когда $n$ нечетно, то оставшиеся ребра должны образовать идеальное совпадение. Эта более сильная гипотеза была проверена для $n=4,5,6,7$ . ^[2]^[16] Для $n=8$ , нечетное число вершин в $O_{n}$ предотвращает существование 8-цветной раскраски ребер, но не исключает возможности разбиения на четыре гамильтоновых цикла.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Биггс, Норман Л. (1976), «Автоморфные графы и условие Крейна», Geometriae Dedicata , 5 (1): 117–127, doi : 10.1007/BF00148146 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Биггс, Норман (1979), «Некоторая странная теория графов», Вторая международная конференция по комбинаторной математике, Анналы Нью-Йоркской академии наук , 319 : 71–81, doi : 10.1111/j.1749-6632.1979.tb32775.x .
^ Уэст, Дуглас Б. (2000), «Упражнение 1.1.28», Введение в теорию графов (2-е изд.), Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, стр. 17 .
^ Jump up to: Перейти обратно: ^а ^б Ван Дам, Эдвин; Хемерс, Виллем Х. (2010), Нечетная характеристика обобщенных нечетных графов , Серия дискуссионных документов CentER № 2010-47, SSRN 1596575 .
^ Ковалевски, А. (1917), «Проблема додекаэдра В. Р. Гамильтона как проблема пестрого порядка», Отчет о сессиях. Академическая наука Вена (Отдел IIа) , 126 : 67–90, 963–1007 . Цитируется Биггсом (1979) .
^ Балабан Александру Т.; Фуркашиу, Д.; Буник, Р. (1966), «Графики множественных 1, 2-сдвигов в ионах карбония и родственных системах», преподобный Рум. Хим. , 11 :1205 .
^ Балабан, Александру Т. (1972), «Химические графики, Часть XIII: Комбинаторные закономерности», Rev. Roumaine Math. Приложение Pures. , 17 : 3–16 .
^ Гафур, Ариф; Башкоу, Теодор Р. (1991), «Исследование нечетных графов как отказоустойчивых межсетевых сетей», IEEE Transactions on Computers , 40 (2): 225–232, doi : 10.1109/12.73594 .
^ Jump up to: Перейти обратно: ^а ^б Биггс, Норман (1972), Гай, Ричард К. (редактор), «Проблема раскраски ребер», Research Issues, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307/2318076 , JSTOR 2318076 .
^ Брауэр, Андриес ; Коэн, Арье М.; Ноймайер, А. (1989), Дистанционно-регулярные графы , ISBN 0-387-50619-5 .
^ Эд Пегг-младший (29 декабря 2003 г.), Кубические симметричные графы , Математические игры, Математическая ассоциация Америки , заархивировано из оригинала 21 августа 2010 г. , получено 24 августа 2010 г.
^ Бабай, Ласло (1995), «Группы автоморфизмов, изоморфизм, реконструкция», у Грэма, Рональда Л .; Гретшель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , том. I, Северная Голландия, стр. 1447–1540, Предложение 1.9, заархивировано из оригинала 11 июня 2010 г.
^ Мун, Аэрюнг (1982), «Характеризация нечетных графов OK _по параметрам», Discrete Mathematics , 42 (1): 91–97, doi : 10.1016/0012-365X(82)90057-7 .
^ Годсил, CD (1980), «Более странная теория графов», Discrete Mathematics , 32 (2): 205–207, doi : 10.1016/0012-365X(80)90055-2 .
^ Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Журнал комбинаторной теории , 8 : 23–29, doi : 10.1016/S0021-9800(70)80005-9 , MR 0266804
^ Jump up to: Перейти обратно: ^а ^б ^с Мередит, Гай Х.Дж.; Ллойд, Э. Кейт (1973), «Футболисты Кроама», Журнал комбинаторной теории, серия B , 15 (2): 161–166, doi : 10.1016/0095-8956(73)90016-6 .
^ Мютце, Торстен; Нумменпало, Джерри; Вальчак, Бартош (2018), «Разреженные графы Кнезера являются гамильтоновыми», STOC'18 — Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений , Нью-Йорк: ACM, стр. 912–919, arXiv : 1711.01636 , MR 3826304

Внешние ссылки

Вайсштейн, Эрик В. , «Нечетный график» , MathWorld

[b76-1] Jump up to: Перейти обратно: ^а ^б Биггс, Норман Л. (1976), «Автоморфные графы и условие Крейна», Geometriae Dedicata , 5 (1): 117–127, doi : 10.1007/BF00148146 .

[b79-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Биггс, Норман (1979), «Некоторая странная теория графов», Вторая международная конференция по комбинаторной математике, Анналы Нью-Йоркской академии наук , 319 : 71–81, doi : 10.1111/j.1749-6632.1979.tb32775.x .

[3] Уэст, Дуглас Б. (2000), «Упражнение 1.1.28», Введение в теорию графов (2-е изд.), Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, стр. 17 .

[vdh10-4] Jump up to: Перейти обратно: ^а ^б Ван Дам, Эдвин; Хемерс, Виллем Х. (2010), Нечетная характеристика обобщенных нечетных графов , Серия дискуссионных документов CentER № 2010-47, SSRN 1596575 .

[5] Ковалевски, А. (1917), «Проблема додекаэдра В. Р. Гамильтона как проблема пестрого порядка», Отчет о сессиях. Академическая наука Вена (Отдел IIа) , 126 : 67–90, 963–1007 . Цитируется Биггсом (1979) .

[6] Балабан Александру Т.; Фуркашиу, Д.; Буник, Р. (1966), «Графики множественных 1, 2-сдвигов в ионах карбония и родственных системах», преподобный Рум. Хим. , 11 :1205 .

[bal72-7] Балабан, Александру Т. (1972), «Химические графики, Часть XIII: Комбинаторные закономерности», Rev. Roumaine Math. Приложение Pures. , 17 : 3–16 .

[8] Гафур, Ариф; Башкоу, Теодор Р. (1991), «Исследование нечетных графов как отказоустойчивых межсетевых сетей», IEEE Transactions on Computers , 40 (2): 225–232, doi : 10.1109/12.73594 .

[b72-9] Jump up to: Перейти обратно: ^а ^б Биггс, Норман (1972), Гай, Ричард К. (редактор), «Проблема раскраски ребер», Research Issues, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307/2318076 , JSTOR 2318076 .

[10] Брауэр, Андриес ; Коэн, Арье М.; Ноймайер, А. (1989), Дистанционно-регулярные графы , ISBN 0-387-50619-5 .

[11] Эд Пегг-младший (29 декабря 2003 г.), Кубические симметричные графы , Математические игры, Математическая ассоциация Америки , заархивировано из оригинала 21 августа 2010 г. , получено 24 августа 2010 г.

[12] Бабай, Ласло (1995), «Группы автоморфизмов, изоморфизм, реконструкция», у Грэма, Рональда Л .; Гретшель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , том. I, Северная Голландия, стр. 1447–1540, Предложение 1.9, заархивировано из оригинала 11 июня 2010 г.

[13] Мун, Аэрюнг (1982), «Характеризация нечетных графов OK _по параметрам», Discrete Mathematics , 42 (1): 91–97, doi : 10.1016/0012-365X(82)90057-7 .

[14] Годсил, CD (1980), «Более странная теория графов», Discrete Mathematics , 32 (2): 205–207, doi : 10.1016/0012-365X(80)90055-2 .

[15] Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Журнал комбинаторной теории , 8 : 23–29, doi : 10.1016/S0021-9800(70)80005-9 , MR 0266804

[el73-16] Jump up to: Перейти обратно: ^а ^б ^с Мередит, Гай Х.Дж.; Ллойд, Э. Кейт (1973), «Футболисты Кроама», Журнал комбинаторной теории, серия B , 15 (2): 161–166, doi : 10.1016/0095-8956(73)90016-6 .

[17] Мютце, Торстен; Нумменпало, Джерри; Вальчак, Бартош (2018), «Разреженные графы Кнезера являются гамильтоновыми», STOC'18 — Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений , Нью-Йорк: ACM, стр. 912–919, arXiv : 1711.01636 , MR 3826304

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]