Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Нечетный график
Граф Кнезера KG (5,2) .svg
O 3 = KG 5,2 - граф Петерсена
Вершины
Края
Диаметрn  - 1 [1] [2]
Обхват3, если n = 2
5, если n = 3
6, если n > 3 [3]
ХарактеристикиДистанционно-транзитивный
ОбозначениеО п
Таблица графиков и параметров
Нечетный граф O 4 = KG 7,3

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

Определение и примеры [ править ]

Нечетный граф O n имеет по одной вершине для каждого из ( n  - 1) -элементных подмножеств (2 n  - 1) -элементного множества. Две вершины соединены ребром тогда и только тогда, когда соответствующие подмножества не пересекаются . [4] То есть O n - граф Кнезера KG (2 n  - 1, n  - 1).

O 2 - это треугольник, а O 3 - знакомый граф Петерсена .

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

История и приложения [ править ]

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

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

Свойства [ править ]

Нечетный граф O n регулярен степени n . У него есть вершины и ребра. Следовательно, количество вершин для n = 1, 2, ... равно

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

Расстояние и симметрия [ править ]

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

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

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

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

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

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

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

Окраска краев [ править ]

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

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

Гамильтоничность [ править ]

Граф Петерсена O 3 - хорошо известный негамильтонов граф, но известно, что все нечетные графы O n для n  ≥ 4 имеют гамильтонов цикл. [18] Поскольку нечетные графы вершинно-транзитивны , они, таким образом, являются одним из частных случаев, для которых известен положительный ответ на гипотезу Ловаса . Биггс [2] высказал более общую гипотезу о том, что ребра O n можно разбить на гамильтоновы циклы с непересекающимися ребрами . Когда n нечетно, оставшиеся края должны образовывать идеальное совпадение. Эта более сильная гипотеза была проверена для n = 4, 5, 6, 7. [2][17] Для n  = 8 нечетное количество вершин в O n предотвращает 8-цветную раскраску ребер, но не исключает возможности разбиения на четыре гамильтоновых цикла.

Ссылки [ править ]

  1. ^ Б Биггс, Норман Л. (1976), "Автоморфные графики и условие Крейна", Geometriae Dedicata , 5 (1): 117-127, DOI : 10.1007 / BF00148146.
  2. ^ a b c d e f g h i Биггс, Норман (1979), "Некоторая странная теория графов", Вторая международная конференция по комбинаторной математике, Annals of the New York Academy of Sciences , 319 : 71–81, doi : 10.1111 / j.1749-6632.1979.tb32775.x.
  3. ^ West, Douglas B. (2000), "Упражнение 1.1.28", Введение в теорию графов (2 - е изд.), Englewood Cliffs, NJ: Prentice-Hall, стр. 17.
  4. ^ Вайсштейн, Эрик В. «Нечетный график» . MathWorld .
  5. ^ а б Ван Дам, Эдвин; Хемерс, Виллем Х. (2010), Нечетная характеристика обобщенных нечетных графов , Серия дискуссионных документов CentER № 2010-47, SSRN 1596575 .
  6. ^ Ковалевский, А. (1917), "Dodekaederaufgabe ALS Buntordnungproblem WR Гамильтон", Sitzungsber. Акад. Wiss. Вена (Abt. IIa) , 126 : 67–90, 963–1007.. Цитируется Биггсом (1979) .
  7. ^ Балабан, Александру Т .; Fǎrcaşiu, D .; Bǎnic, R. (1966), "Графики множественных 1,2-сдвигов в ионах карбония и родственных системах", Rev. Roum. Чим. , 11 : 1205.
  8. ^ Балабан, Александру Т. (1972), "Химические графы, Часть XIII: Комбинаторные шаблоны", Rev. Roumaine Math. Pures Appl. , 17 : 3–16.
  9. ^ Гафур, Ариф; Bashkow, Theodore R. (1991), "Исследование нечетных графов , как отказоустойчивые сети передачи", IEEE Transactions на компьютерах , 40 (2): 225-232, DOI : 10,1109 / 12,73594.
  10. ^ Б Биггс, Норман (1972), Гай, Ричард К. (ред.), "Ребро-раскраска проблема", проблемы исследования, American Mathematical Monthly , 79 (9): 1018-1020, DOI : 10,2307 / 2318076 , JSTOR 2318076 .
  11. ^ Брауэр, Андрис ; Cohen, Arjeh M .; Neumaier, A. (1989), дистанционно-регулярные графы , ISBN 0-387-50619-5.
  12. ↑ Эд Пегг-младший (29 декабря 2003 г.), Кубические симметричные графы , Математические игры, Математическая ассоциация Америки , заархивировано из оригинала 21 августа 2010 г. , извлечено 24 августа 2010 г..
  13. ^ Бабай, Ласло (1995), "Группы автоморфизмов, изоморфизм, реконструкция", у Грэма, Рональда Л .; Грёчель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , I , Северная Голландия, стр. 1447–1540, Предложение 1.9, архивировано с оригинала 11 июня 2010 г..
  14. ^ Мун, Aeryung (1982), "Характеризация нечетных графов O k параметрами", Дискретная математика , 42 (1): 91–97, DOI : 10.1016 / 0012-365X (82) 90057-7.
  15. ^ Godsil, компакт - диск (1980), "Больше нечетные теории графов", дискретная математика , 32 (2): 205-207, DOI : 10.1016 / 0012-365X (80) 90055-2.
  16. ^ Уоткинс, Марк Э. (1970), «Связность транзитивных графов», Журнал комбинаторной теории , 8 : 23–29, DOI : 10.1016 / S0021-9800 (70) 80005-9 , MR 0266804 
  17. ^ a b c Мередит, Гай HJ; Ллойд, Э. Кейт (1973), «Футболисты Кроама», Журнал комбинаторной теории, серия B , 15 (2): 161–166, DOI : 10.1016 / 0095-8956 (73) 90016-6.
  18. ^ Мютце, Торстен; Нумменпало, Джерри; Вальчак, Бартош (2018), «Разреженные графы Кнезера являются гамильтоновыми», STOC'18 - Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений , Нью-Йорк: ACM, стр. 912–919, arXiv : 1711.01636 , MR 3826304