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

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

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

Определения и примеры[править | править вики-текст]

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

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

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

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

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

Свойства[править | править вики-текст]

Нечётный граф On является регулярным графом степени n. Он имеет \tbinom {2n-1}{n-1} вершин и n\tbinom {2n-1}{n-1}/2 рёбер. Таким образом, число вершин для 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 известны как обобщённые нечётные графы и включают складные кубические графы[en] так же как и сами нечётные графы.[5]

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

Пусть On — нечётный граф, определённый на (2n − 1)-элементных подмножествах множества X, и пусть x — элементы ножества X. Тогда среди вершин On ровно \tbinom{2n-2}{n-2} вершин соответствуют множествам, которые содержат x. Поскольку все эти множества содержат x, они не являются непересекающимися, и образуют независимое множество графа On. Таким образом, On имеет 2n − 1 различных независимых множеств размера \tbinom{2n-2}{n-2}. Из теоремыа Эрдёша–Ко–Радо[en] следует, что это максимальные независимые множеств графа On. Таким образом, число независимости графа On равно \tbinom{2n-2}{n-2}. Более того, любое максимальное независимое множество должно иметь этот вид, так что 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) на floor(n/2) гамильтоновых циклов. Если n нечётно, оставшиеся рёбра образуют совершенное сочетание.[2][16] Для n = 8, нечётное число вершин в On не позволяет раскрасить рёбра в 8 цветов, но не закрывает возможность разложения на четыре гамильтоновых цикла.

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

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

  1. 1 2 Norman L. Biggs Automorphic graphs and the Krein condition // Geometriae Dedicata. — 1976. — В. 1. — Т. 5. — С. 117–127. — DOI:10.1007/BF00148146.
  2. 1 2 3 4 5 6 7 8 Norman Biggs Second International Conference on Combinatorial Mathematics. — 1979. — Т. 319. — С. 71–81. — DOI:10.1111/j.1749-6632.1979.tb32775.x.
  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. 1 2 Edwin Van Dam, Willem H. Haemers An Odd Characterization of the Generalized Odd Graphs. — 2010.
  6. 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. 1 2 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. — В. 2. — Т. 40. — С. 225–232. — DOI:10.1109/12.73594.
  10. 1 2 Norman Biggs Research Problems // American Mathematical Monthly. — 1972. — Т. 79. — С. 1018–1020..
  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..
  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. — В. 1. — Т. 42. — С. 91–97. — DOI:10.1016/0012-365X(82)90057-7.
  15. C. D. Godsil More odd graph theory // Discrete Mathematics. — 1980. — В. 2. — Т. 32. — С. 205–207. — DOI:10.1016/0012-365X(80)90055-2
  16. 1 2 3 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..