Непарний граф
В теорії графів непа́рні гра́фи On — це сімейство симетричних графів із високим непарним обхватом, визначених на деяких сімействах множин. Вони включають і узагальнюють графи Петерсена.
Непарний граф On має одну вершину для кожної з (n − 1)-елементних підмножин множини з (2n — 1) елементів. Дві вершини пов'язані ребром тоді й лише тоді, якщо відповідні підмножини не перетинаються[4]. Так, On — це граф Кнезера KG(2n − 1,n − 1), O2 — трикутник, а O3 — знайомий граф Петерсена.
Узага́льнені непа́рні гра́фи включають непарні графи і складані кубічні графи[en], і визначаються як дистанційно-регулярні графи з діаметром n − 1 і непарним обхватом 2n − 1 для деякого n[5].
Хоча графи Петерсена відомі від 1898 року, їх визначення як «непарних графів» датується роботою Ковальовскі[6], в якій він вивчає непарний граф O4[2][6]. Непарні графи вивчають з огляду на їх використання в хімічній теорії графів під час моделювання зсуву йонів вуглецю[en][7][8]. Їх також використовують як мережеву топологію при паралельних обчисленнях[9].
Позначення On для цих графів запропонував 1972 року[10] Норман Біггз[en]. Біггз і Тоні Гардинер[en] пояснюють назву непарних графів у неопублікованій монографії 1974 року — кожному ребру непарного графа можна зіставити єдиний елемент X, який є «odd man out» (що можна перекласти як «гравець без партнера виходить зі гри»), тобто елемент не належить жодній іншій підмножині, пов'язаній із вершинами, інцидентними даному ребру[11][12].
Непарний граф On є регулярним графом степеня n. Він має вершин і ребер. Таким чином, число вершин для 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 рівно вершин відповідають множинам, які містять x. Оскільки всі ці множини містять x, вони не є неперетинними, і утворюють незалежну множину графа On. Таким чином, On має 2n − 1 різних незалежних множин розміру . Із теореми Ердеша — Ко — Радо[en] випливає, що це максимальні незалежні множини графа On. Таким чином, число незалежності графа On дорівнює Більш того, будь-яка максимальна незалежна множина повинна мати такий вигляд, так що 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 має гамільтонів цикл.
- ↑ а б Norman L. Biggs. Automorphic graphs and the Krein condition // Geometriae Dedicata. — 1976. — Вип. 5 (18 червня). — С. 117—127. — DOI: .
- ↑ а б в г д е ж и 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. — 18 червня.
- ↑ а б A. Kowalewski. W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem // Sitzungsber. Akad. Wiss. Wien (Abt. IIa). — 1917. — Т. 126 (18 червня). — С. 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 (18 червня). — С. 1205.
- ↑ а б Alexandru T. Balaban. Chemical graphs, Part XIII: Combinatorial patterns // Rev. Roumaine Math. Pures Appl.. — 1972. — Т. 17 (18 червня). — С. 3—16.
- ↑ Arif Ghafoor, Theodore R. Bashkow. A study of odd graphs as fault-tolerant interconnection networks // IEEE Transactions on Computing. — 1991. — Т. 40, вип. 2 (18 червня). — С. 225—232. — DOI: .
- ↑ а б Norman Biggs. Research Problems // American Mathematical Monthly. — 1972. — Т. 79, вип. 9 (18 червня). — С. 1018—1020.
- ↑ Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Distance-regular Graphs. — 1989. — 18 червня. — ISBN 0-387-50619-5.
- ↑ Ed Pegg, Jr. Cubic Symmetric Graphs. — Mathematical Association of America, 2003. — 18 червня. Архівовано з джерела 21 серпня 2010.
- ↑ László Babai. [1] / 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 Ok by parameters // Discrete Mathematics. — 1982. — Т. 42, вип. 1 (18 червня). — С. 91—97. — DOI: .
- ↑ C. D. Godsil. More odd graph theory // Discrete Mathematics. — 1980. — Т. 32, вип. 2 (18 червня). — С. 205—207. — DOI: .
- ↑ а б в Guy H. J. Meredith, E. Keith Lloyd. The footballers of Croam // Journal of Combinatorial Theory, Series B. — 1973. — Т. 15 (18 червня). — С. 161—166. — DOI: .
- ↑ Guy H. J. Meredith, E. Keith Lloyd. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). — Southend : Inst. Math. Appl, 1972. — 18 червня. — С. 229—236.
- ↑ Michael Mather. The Rugby footballers of Croam // Journal of Combinatorial Theory, Series B. — 1976. — Т. 20 (18 червня). — С. 62—63. — DOI: .
- ↑ Ian Shields, Carla D. Savage. A note on Hamilton cycles in Kneser graphs // Bulletin of the Institute for Combinatorics and Its Applications. — 2004. — Т. 40 (18 червня). — С. 13—22. Архівовано з джерела 30 серпня 2017. Процитовано 2022-03-03.
- Norman Biggs. Second International Conference on Combinatorial Mathematics. — 1979. — Т. 319 (18 червня). — С. 71—81. — DOI: .