PROFILPELAJAR.COM

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

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

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

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

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

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

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

Свойства

Нечётный граф O_n является регулярным графом степени 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).

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

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

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

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

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

Пусть O_n — нечётный граф, определённый на (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₃ оно равно n + 1. Если n — степень двух, число вершин в графе нечётно, откуда опять следует, что число цветов в рёберной раскраске равно n + 1^[16]. Однако O₅, O₆ и O₇ могут быт раскрашены n цветами^[2]^[16].

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

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

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

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

Примечания

↑ ¹ ² Norman L. Biggs. Automorphic graphs and the Krein condition // Geometriae Dedicata. — 1976. — Вып. 5. — С. 117—127. — doi:10.1007/BF00148146.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ Biggs, 1979
↑ Douglas B. West. Introduction to Graph Theory. — 2nd. — Englewood Cliffs, NJ: Prentice-Hall, 2000. — С. 17.
↑ Weisstein, Eric W. Odd Graph (англ.) на сайте Wolfram MathWorld.
↑ ¹ ² Edwin Van Dam, Willem H. Haemers. An Odd Characterization of the Generalized Odd Graphs. — 2010.
↑ ¹ ² A. Kowalewski. W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem // Sitzungsber. Akad. Wiss. Wien (Abt. IIa). — 1917. — Т. 126. — С. 67—90, 963—1007. Как цитировано у Биггса (Biggs 1979).
↑ 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.
↑ ¹ ² Alexandru T. Balaban. Chemical graphs, Part XIII: Combinatorial patterns // Rev. Roumaine Math. Pures Appl.. — 1972. — Т. 17. — С. 3—16.
↑ 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.
↑ ¹ ² Norman Biggs. Research Problems // American Mathematical Monthly. — 1972. — Т. 79, вып. 9. — С. 1018—1020. — JSTOR 2318076.
↑ Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Distance-regular Graphs. — 1989. — ISBN 0-387-50619-5.
↑ Ed Pegg, Jr. Cubic Symmetric Graphs. — Mathematical Association of America, 2003. Архивировано 21 августа 2010 года.
↑ László Babai. Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. — North-Holland, 1995. — Т. I. — С. 1447—1540. Архивировано 11 июня 2010 года.
↑ Aeryung Moon. Characterization of the odd graphs O_k by parameters // Discrete Mathematics. — 1982. — Т. 42, вып. 1. — С. 91—97. — doi:10.1016/0012-365X(82)90057-7.
↑ C. D. Godsil. More odd graph theory // Discrete Mathematics. — 1980. — Т. 32, вып. 2. — С. 205—207. — doi:10.1016/0012-365X(80)90055-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.
↑ Guy H. J. Meredith, E. Keith Lloyd. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). — Southend: Inst. Math. Appl, 1972. — С. 229—236.
↑ 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.
↑ 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.

Литература

Norman Biggs. Second International Conference on Combinatorial Mathematics. — 1979. — Т. 319. — С. 71—81. — doi:10.1111/j.1749-6632.1979.tb32775.x.

[b76-1] ¹ ² Norman L. Biggs. Automorphic graphs and the Krein condition // Geometriae Dedicata. — 1976. — Вып. 5. — С. 117—127. — doi:10.1007/BF00148146.

[b79-2] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ 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.

[vdh10-5] ¹ ² Edwin Van Dam, Willem H. Haemers. An Odd Characterization of the Generalized Odd Graphs. — 2010.

[Kow1917-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.

[bal72-8] ¹ ² 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.

[b72-10] ¹ ² 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. Архивировано 11 июня 2010 года.

[14] Aeryung Moon. Characterization of the odd graphs O_k 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.

[el73-16] ¹ ² ³ 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

PROFILPELAJAR.COM

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

Содержание

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

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

Свойства

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

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

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

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

Примечания

Литература

Read other articles:

Dewan Perwakilan Rakyat Daerah Kota Pematangsiantar

Chengdu

رسالة علي بن أبي طالب إلى مالك الأشتر

مخلفات فضائية

Mina Leonesi

Big Lagoon Rancheria

Sabiñánigo

Matt Haney

2005–06 A1 Grand Prix season

Premio César

Valentine - Appuntamento con la morte

Shatranj Ke Khilari

Jessica Baker (politician)

Weybourne, Norfolk

Climatology

Gerakan Tani Indonesia

Norden

Molecular orbital

Norton Priory

ムラート