Перегляд вихідного коду сторінки Непарний граф

[[Файл:Kneser_graph_KG(5,2).svg|міні|200x200пкс|Граф Петерсена ''O''<sub>3</sub> = KG<sub>5,2</sub>
<br/>вершина = <math>\tbinom {2n-1}{n-1}</math>
<br/>ребер = <math>n\tbinom {2n-1}{n-1}/2</math>
<br/>діаметр = ''n''&nbsp;−&nbsp;1<ref name="b76">{{Стаття|author=Norman L. Biggs|doi=10.1007/BF00148146|видання=Geometriae Dedicata|pages=117—127|title=Automorphic graphs and the Krein condition|issue=5|date=1976}}</ref><ref name="b79">{{Sfn0|Biggs|1979}}</ref>
<br/>обхват=
<br/>  3 якщо ''n'' = 2,
<br/>  5 якщо ''n'' = 3,
<br/>  6 якщо ''n'' > 3<ref>{{Книга
|автор = Douglas B. West
|видання = 2nd
|місце = Englewood Cliffs, NJ
|сторінки = 17
|видавництво = Prentice-Hall
|заголовок = Introduction to Graph Theory
|рік = 2000
}}</ref>
<br/>властивість = [[Дистанційно-транзитивний граф|дистанційно-транзитивний]]
<br/>позначення = ''O<sub>n</sub>'']]
[[Файл:Odd_graph_O4.svg|міні|362x362пкс|Непарний граф ''O''<sub>4</sub> = KG<sub>7,3</sub>]]
В [[Теорія графів|теорії графів]] '''непа́рні гра́фи''' ''O<sub>n</sub>''&nbsp;— це сімейство [[Симетричний граф|симетричних графів]] із високим [[Обхват (теорія графів)|непарним обхватом]], визначених на деяких [[Множина|сімействах множин]]. Вони включають і узагальнюють [[Граф Петерсена|графи Петерсена]].

== Визначення та приклади ==
Непарний граф ''O<sub>n</sub>'' має одну [[Вершина (теорія графів)|вершину]] для кожної з (''n'' − 1)-елементних підмножин множини з (2''n''&nbsp;— 1) елементів. Дві вершини пов'язані ребром [[тоді й лише тоді]], якщо відповідні підмножини не перетинаються<ref>{{MathWorld|title=Odd Graph|urlname=OddGraph}}</ref>. Так, ''O<sub>n</sub>''&nbsp;— це [[Кнезерів граф|граф Кнезера]] ''KG''(2''n'' − 1,''n'' − 1), ''O''<sub>2</sub>&nbsp;— трикутник, а ''O''<sub>3</sub>&nbsp;— знайомий [[граф Петерсена]].

'''Узага́льнені непа́рні гра́фи''' включають непарні графи і {{Iw|Складаний кубічний граф|складані кубічні графи|en|folded cube graph}}, і визначаються як [[Дистанційно-регулярний граф|дистанційно-регулярні графи]] з [[Відстань (теорія графів)|діаметром]] ''n'' − 1 і непарним обхватом 2''n'' − 1 для деякого ''n''<ref name="vdh10">{{Стаття|author=Edwin Van Dam, Willem H. Haemers|серія=CentER Discussion Paper Series No. 2010-47|title=An Odd Characterization of the Generalized Odd Graphs|date=2010}}</ref>.

== Історія та застосування ==
Хоча графи Петерсена відомі від [[1898]] року, їх визначення як «непарних графів» датується роботою Ковальовскі<ref name="Kow1917" />, в якій він вивчає непарний граф ''O''<sub>4</sub><ref name="b79"/><ref name="Kow1917">{{Стаття|author=A. Kowalewski|видання=Sitzungsber. Akad. Wiss. Wien (Abt. IIa)|pages=67—90, 963—1007|title=W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem|том=126|date=1917}} Як процитовано в Біггза {{Harvard citation|Biggs|1979}}.</ref>. Непарні графи вивчають з огляду на їх використання в [[Хімічна теорія графів|хімічній теорії графів]] під час моделювання зсуву {{Iw|Йони вуглецю|йонів вуглецю|en|carbonium ion}}<ref>{{Стаття|author=Alexandru T. Balaban, D. Fǎrcaşiu, R. Bǎnicǎ|видання=Rev. Roum. Chim.|pages=1205|title=Graphs of multiple 1, 2-shifts in carbonium ions and related systems|том=11|date=1966}}</ref><ref name="bal72">{{Стаття|author=Alexandru T. Balaban|видання=Rev. Roumaine Math. Pures Appl.|pages=3—16|title=Chemical graphs, Part XIII: Combinatorial patterns|том=17|date=1972}}</ref>. Їх також використовують як [[Топологія мереж|мережеву топологію]] при [[Паралельні обчислення|паралельних обчисленнях]]<ref>{{Стаття||author=Arif Ghafoor, Theodore R. Bashkow|doi=10.1109/12.73594|issue=2|видання=IEEE Transactions on Computing|pages=225—232|title=A study of odd graphs as fault-tolerant interconnection networks|том=40|date=1991}}</ref>.

Позначення ''O<sub>n</sub>'' для цих графів запропонував [[1972 у науці|1972]] року<ref name="b72">{{Стаття|author=Norman Biggs|issue=9|видання=American Mathematical Monthly|pages=1018—1020|title=Research Problems|url=https://archive.org/details/sim_american-mathematical-monthly_1972-11_79_9/page/1018|том=79|date=1972}}</ref> {{Iw|Норман Біггз||en|Norman Biggs (mathematician)}}. Біггз і {{Iw|Тоні Гардинер||en|Tony Gardiner}} пояснюють назву непарних графів у неопублікованій монографії 1974 року&nbsp;— кожному ребру непарного графа можна зіставити єдиний елемент ''X'', який є «odd man out» (що можна перекласти як «гравець без партнера виходить зі гри»), тобто елемент не належить жодній іншій підмножині, пов'язаній із вершинами, інцидентними даному ребру<ref>{{Стаття|author=Andries Brouwer, Arjeh M. Cohen, A. Neumaier|isbn=0-387-50619-5|title=Distance-regular Graphs|date=1989}}</ref><ref>{{Стаття|author=Ed Pegg, Jr.|date=2003|publisher=[[Mathematical Association of America]]|серія=Math Games|title=Cubic Symmetric Graphs|url=http://maa.org/editorial/mathgames/mathgames_12_29_03.html|archiveurl=https://web.archive.org/web/20100821184232/http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html|archivedate=2010-08-21}}</ref>.

== Властивості ==
Непарний граф ''O''<sub>''n''</sub> є регулярним графом степеня ''n''. Він має <math>\tbinom {2n-1}{n-1}</math> вершин і <math>n\tbinom {2n-1}{n-1}/2</math> ребер. Таким чином, число вершин для ''n'' = 1, 2, … буде

: 1, 3, 10, 35, 126, 462, 1716, 6435 ({{OEIS|A001700}}).

=== Дистанція і симетрія ===
Якщо дві вершини в ''O''<sub>''n''</sub> відповідають множинам однакового розміру, що відрізняються ''k'' елементами, то можна отримати з першої другу за 2''k'' кроків, на кожному кроці прибираючи або додаючи один елемент. Якщо 2''k'' < ''n'', то це [[Задача про найкоротший шлях|найкоротший шлях]]. В іншому випадку можна знайти коротший шлях цього типу, якщо почати з доповняльної до другої множини, а потім отримати другу множину, зробивши ще один крок. Таким чином, [[Відстань (теорія графів)|діаметр]] графа ''O''<sub>''n''</sub> дорівнює ''n'' − 1<ref name="b76"/><ref name="b79"/>.

Будь-який непарний граф [[Симетричний граф|3-дуго-транзитивний]]&nbsp;— будь-який орієнтований триреберний шлях у непарному графі можна перевести в будь-який такий самий шлях за допомогою симетрії графа<ref>{{Книга
|автор = László Babai
|заголовок = Handbook of Combinatorics
|посилання = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps
|сторінки = 1447—1540
|відповідальний = Ronald L. Graham, Martin Grötschel, László Lovász
|том = I
|видавництво = North-Holland
|рік = 1995
|назва = 
|archivedate = 2010-06-11
|archiveurl = https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps
}}</ref>. Непарні графи [[Дистанційно-транзитивний граф|дистанційно-транзитивні]], оскільки вони [[Дистанційно-регулярний граф|дистанційно-регулярні]]<ref name="b79"/>. Як дистанційно-регулярні графи, вони однозначно визначаються своїм масивом перетинів&nbsp;— ніякий інший дистанційно-регулярний граф не може мати таких самих параметрів, що й непарний граф<ref>{{Стаття|author=Aeryung Moon|doi=10.1016/0012-365X(82)90057-7|issue=1|видання=Discrete Mathematics|pages=91—97|title=Characterization of the odd graphs ''O<sub>k</sub>'' by parameters|том=42|date=1982}}</ref>. Однак всупереч високому ступеню симетрії, непарні графи ''O<sub>n</sub>'' для ''n'' > 2 ніколи не є [[Граф Келі|графами Келі]]<ref>{{Стаття|author=C. D. Godsil|doi=10.1016/0012-365X(80)90055-2|issue=2|видання=Discrete Mathematics|pages=205—207|title=More odd graph theory|том=32|date=1980}}</ref>.

Непарні графи з ''n'' ≥ 3 мають [[Обхват (теорія графів)|обхват]] шість. Однак, хоча вони і не є [[Двочастковий граф|двочастковими графами]], їхні непарні цикли набагато довші, а саме непарний граф ''O<sub>n</sub>'' має непарний обхват 2''n'' − 1. Якщо ''n''-регулярний граф має діаметр ''n'' − 1, непарний обхват 2''n'' − 1 і тільки ''n'' різних [[Власні вектори та власні значення|власних значень]], він повинен бути дистанційно-регулярним. Дистанційно-регулярні графи діаметра ''n'' − 1 і непарного обхвату 2''n'' − 1 відомі як '''узага́льнені непа́рні гра́фи''' і включають {{Iw|Складаний кубічний граф|складані кубічні графи|en|folded cube graph}} так само, як і самі непарні графи<ref name="vdh10"/>.

=== Незалежні множини і розмальовка вершин ===
Нехай ''O<sub>n</sub>''&nbsp;— непарний граф, визначений на (2''n'' − 1)-елементних підмножинах множини ''X'', і нехай ''x''&nbsp;— елементи множини ''X''. Тоді серед вершин ''O<sub>n</sub>'' рівно <math>\tbinom{2n-2}{n-2}</math> вершин відповідають множинам, які містять ''x''. Оскільки всі ці множини містять ''x'', вони не є неперетинними, і утворюють [[Задача про незалежну множину|незалежну множину]] графа ''O<sub>n</sub>''. Таким чином, ''O<sub>n</sub>'' має 2''n'' − 1 різних незалежних множин розміру <math>\tbinom{2n-2}{n-2}</math>. Із {{Iw|Теорема Ердеша — Ко — Радо|теореми Ердеша — Ко — Радо|en|Erdős–Ko–Rado theorem}} випливає, що це [[Задача про незалежну множину|максимальні незалежні множини]] графа ''O<sub>n</sub>''. Таким чином, [[число незалежності]] графа ''O<sub>n</sub>'' дорівнює <math>\tbinom{2n-2}{n-2}.</math> Більш того, будь-яка максимальна незалежна множина повинна мати такий вигляд, так що ''O<sub>n</sub>'' має рівно 2''n'' − 1 максимальних незалежних множин<ref name="b79"/>.

Якщо ''I''&nbsp;— максимальна незалежна множина, утворена множиною, яка містить елемент ''x'', то [[Доповнення множин|доповнення]] множини ''I''&nbsp;— це множина вершин, що не містять ''x''. Це доповнення [[Словник термінів теорії графів|породжує]] [[Парування (теорія графів)|парування]] в ''G''. Кожна вершина незалежної множини суміжна ''n'' вершинам парування, а кожна вершина парування суміжна ''n'' − 1 вершинам незалежної множини<ref name="b79"/>. Зважаючи на цей розклад і з огляду на те, що непарні графи не є двочастковими, вони мають [[хроматичне число]] рівне трьом&nbsp;— вершинам максимальної незалежної множини можна призначити один колір, а два інших кольори отримаємо з парування, породженого доповненням.

=== Реберне розфарбування ===
За [[Теорема Візінга|теоремою Візінга]] число кольорів, необхідних для [[Розфарбовування ребер|розфарбування ребер]] непарного графа ''O''<sub>''n''</sub>, дорівнює або ''n'', або ''n'' + 1, і у випадку графів Петерсена ''O''<sub>3</sub> воно дорівнює ''n'' + 1. Якщо ''n''&nbsp;— степінь двох, число вершин у графі непарне, звідки знову випливає, що число кольорів у реберному розфарбуванні дорівнює ''n'' + 1<ref name="el73">{{Стаття|author=Guy H. J. Meredith, E. Keith Lloyd|doi=10.1016/0095-8956(73)90016-6|видання=Journal of Combinatorial Theory, Series B|pages=161—166|title=The footballers of Croam|том=15|date=1973}}</ref>. Однак ''O''<sub>5</sub>, ''O''<sub>6</sub> і ''O''<sub>7</sub> можна розфарбувати ''n'' кольорами<ref name="b79"/><ref name="el73" />.

Біггз<ref name="b72"/> пояснює цю задачу такою історією: одинадцять [[футбол]]істів у вигаданому місті Кроам хочуть утворити пари команд для [[Футзал|міні-футболу]] (одна людина залишається судити зустріч) усіма 1386 різними способами і хочуть скласти розклад ігор між усіма парами, при цьому шість ігор кожної команди мають гратися в різні дні тижня, за відсутності ігор у неділю. Чи можливо це? У цій історії кожна гра представляє ребро ''O''<sub>6</sub>, всі дні представлені кольорами, а реберне розфарбування в 6 кольорів графа ''O''<sub>6</sub> дає розклад.

=== Непарні графи і гамільтонові графи ===
Граф Петерсена ''O''<sub>3</sub>&nbsp;— це добре відомий негамільтонів граф, але було показано, що графи від ''O''<sub>4</sub> до ''O''<sub>14</sub> містять [[Гамільтонів граф|гамільтонові цикли]]<ref name="bal72"/><ref>{{Стаття|author=Guy H. J. Meredith, E. Keith Lloyd|place=Southend|pages=229—236|publisher=Inst. Math. Appl|title=Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972)|date=1972}}</ref><ref>{{Стаття|author=Michael Mather|doi=10.1016/0095-8956(76)90066-6|видання=Journal of Combinatorial Theory, Series B|pages=62—63|title=The Rugby footballers of Croam|том=20|date=1976}}</ref><ref>{{Стаття|author=Ian Shields, Carla D. Savage|видання=Bulletin of the Institute for Combinatorics and Its Applications|pages=13—22|title=A note on Hamilton cycles in Kneser graphs|url=http://www.cybershields.com/publications/kneser3.pdf|том=40|date=2004|accessdate=2022-03-03|archivedate=2017-08-30|archiveurl=https://web.archive.org/web/20170830054425/http://www.cybershields.com/publications/kneser3.pdf}}</ref>. Строгіше, комбінуючи задачу пошуку гамільтонових циклів і реберного розфарбування, можна розбити ребра графа ''O''<sub>''n''</sub> (для ''n'' = 4, 5, 6, 7) на найближче знизу ціле від (''n''/2) гамільтонових циклів. Якщо ''n'' непарне, решта ребер утворюють досконале поєднання<ref name="b79"/><ref name="el73"/>. Для ''n'' = 8, непарне число вершин в ''O''<sub>''n''</sub> не дозволяє розфарбувати ребра у 8 кольорів, але не закриває можливості [[Гамільтонів розклад|розкладання на чотири гамільтонових цикли]].

[[Гіпотеза Ловаса про гамільтонів цикл]] припускає, що кожен непарний граф має гамільтонів шлях і що кожен непарний граф ''O<sub>n</sub>'' з ''n'' ≥ 4 має гамільтонів цикл.

== Примітки ==
{{примітки|2}}

== Література ==
* {{Стаття|author=Norman Biggs|серія=Annals of the New York Academy of Sciences|том=319|title=Second International Conference on Combinatorial Mathematics|pages=71—81|date=1979|doi=10.1111/j.1749-6632.1979.tb32775.x|ref=Biggs}}
{{Бібліоінформація}}
[[Категорія:Параметричні сімейства графів]]
[[Категорія:Регулярні графи]]