Нечётный граф

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Граф Петерсена O3 = KG5,2
вершин = [math]\displaystyle{ \tbinom {2n-1}{n-1} }[/math]
ребер = [math]\displaystyle{ n\tbinom {2n-1}{n-1}/2 }[/math]
диаметр = n − 1[1][2]
обхват=
  3 если n = 2,
  5 если n = 3,
  6 если n > 3[3]
свойства = дистанционно-транзитивен
обозначение = On
Нечётный граф O4 = KG7,3

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

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

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

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

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

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

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

Свойства

Нечётный граф On является регулярным графом степени n. Он имеет [math]\displaystyle{ \tbinom {2n-1}{n-1} }[/math] вершин и [math]\displaystyle{ n\tbinom {2n-1}{n-1}/2 }[/math] рёбер. Таким образом, число вершин для n = 1, 2,… будет

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

Дистанция и симметрия

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

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

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

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

Пусть On — нечётный граф, определённый на (2n − 1)-элементных подмножествах множества X, и пусть x — элементы множества X. Тогда среди вершин On ровно [math]\displaystyle{ \tbinom{2n-2}{n-2} }[/math] вершин соответствуют множествам, которые содержат x. Поскольку все эти множества содержат x, они не являются непересекающимися, и образуют независимое множество графа On. Таким образом, On имеет 2n − 1 различных независимых множеств размера [math]\displaystyle{ \tbinom{2n-2}{n-2} }[/math]. Из теоремы Эрдёша – Ко – Радо[англ.] следует, что это максимальные независимые множеств графа On. Таким образом, число независимости графа On равно [math]\displaystyle{ \tbinom{2n-2}{n-2}. }[/math] Более того, любое максимальное независимое множество должно иметь этот вид, так что On имеет в точности 2n − 1 максимальных независимых множеств[2].

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

Рёберная раскраска

По теореме Визинга число цветов, необходимых для раскраски рёбер нечётного графа On, равно либо n, либо n + 1, и в случае графов Петерсена O3 оно равно n + 1. Если n — степень двух, число вершин в графе нечётно, откуда опять следует, что число цветов в рёберной раскраске равно n + 1[16]. Однако O5, O6 и O7 могут быт раскрашены n цветами[2][16].

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

Нечётные графы и гамильтоновы графы

Граф Петерсена O3 — это хорошо известные негамильтоновы графы, но было показано, что графы от O4 до O14 содержат гамильтоновы циклы[8][17][18][19]. Более строго, комбинируя задачи поиска гамильтоновых циклов и рёберной раскраски, можно разбить рёбра графа On (для n = 4, 5, 6, 7) на ближайшее снизу целое от (n/2) гамильтоновых циклов. Если n нечётно, оставшиеся рёбра образуют совершенное сочетание[2][16]. Для n = 8, нечётное число вершин в On не позволяет раскрасить рёбра в 8 цветов, но не закрывает возможность разложения на четыре гамильтоновых цикла.

Гипотеза Ловаса о гамильтоновом цикле предполагает, что каждый нечётный граф имеет гамильтонов путь и что каждый нечётный граф On с n ≥ 4 имеет гамильтонов цикл.

Примечания

  1. ↑ 1,0 1,1 Norman L. Biggs. Automorphic graphs and the Krein condition // Geometriae Dedicata. — 1976. — Вып. 5. — С. 117—127. — doi:10.1007/BF00148146.
  2. ↑ 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 Biggs, 1979
  3. ↑ Douglas B. West. Introduction to Graph Theory. — 2nd. — Englewood Cliffs, NJ: Prentice-Hall, 2000. — С. 17.
  4. ↑ Weisstein, Eric W. Odd Graph (англ.) на сайте Wolfram MathWorld.
  5. ↑ 5,0 5,1 Edwin Van Dam, Willem H. Haemers. An Odd Characterization of the Generalized Odd Graphs. — 2010.
  6. ↑ 6,0 6,1 A. Kowalewski. W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem // Sitzungsber. Akad. Wiss. Wien (Abt. IIa). — 1917. — Т. 126. — С. 67—90, 963—1007. Как цитировано у Биггса (Biggs 1979).
  7. ↑ Alexandru T. Balaban, D. Fǎrcaşiu, R. Bǎnicǎ. Graphs of multiple 1, 2-shifts in carbonium ions and related systems // Rev. Roum. Chim.. — 1966. — Т. 11. — С. 1205.
  8. ↑ 8,0 8,1 Alexandru T. Balaban. Chemical graphs, Part XIII: Combinatorial patterns // Rev. Roumaine Math. Pures Appl.. — 1972. — Т. 17. — С. 3—16.
  9. ↑ Arif Ghafoor, Theodore R. Bashkow. A study of odd graphs as fault-tolerant interconnection networks // IEEE Transactions on Computing. — 1991. — Т. 40, вып. 2. — С. 225—232. — doi:10.1109/12.73594.
  10. ↑ 10,0 10,1 Norman Biggs. Research Problems // American Mathematical Monthly. — 1972. — Т. 79, вып. 9. — С. 1018—1020. — JSTOR 2318076.
  11. ↑ Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Distance-regular Graphs. — 1989. — ISBN 0-387-50619-5.
  12. ↑ Ed Pegg, Jr. Cubic Symmetric Graphs. — Mathematical Association of America, 2003. Архивировано 21 августа 2010 года.
  13. ↑ László Babai. Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. — North-Holland, 1995. — Т. I. — С. 1447—1540.
  14. ↑ Aeryung Moon. Characterization of the odd graphs Ok by parameters // Discrete Mathematics. — 1982. — Т. 42, вып. 1. — С. 91—97. — doi:10.1016/0012-365X(82)90057-7.
  15. ↑ C. D. Godsil. More odd graph theory // Discrete Mathematics. — 1980. — Т. 32, вып. 2. — С. 205—207. — doi:10.1016/0012-365X(80)90055-2.
  16. ↑ 16,0 16,1 16,2 Guy H. J. Meredith, E. Keith Lloyd. The footballers of Croam // Journal of Combinatorial Theory, Series B. — 1973. — Т. 15. — С. 161—166. — doi:10.1016/0095-8956(73)90016-6.
  17. ↑ Guy H. J. Meredith, E. Keith Lloyd. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). — Southend: Inst. Math. Appl, 1972. — С. 229—236.
  18. ↑ Michael Mather. The Rugby footballers of Croam // Journal of Combinatorial Theory, Series B. — 1976. — Т. 20. — С. 62—63. — doi:10.1016/0095-8956(76)90066-6.
  19. ↑ Ian Shields, Carla D. Savage. A note on Hamilton cycles in Kneser graphs // Bulletin of the Institute for Combinatorics and Its Applications. — 2004. — Т. 40. — С. 13—22.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Нечётный_граф&oldid=12899451