Непарний граф

Граф Петерсена O₃ = KG_5,2
вершина = ${\tbinom {2n-1}{n-1}}$
ребер = $n{\tbinom {2n-1}{n-1}}/2$
діаметр = n − 1
обхват=
  3 якщо n = 2,
  5 якщо n = 3,
  6 якщо n > 3
властивість = дистанційно-транзитивний
позначення = O_n

Непарний граф O₄ = KG_7,3

В теорії графів непа́рні гра́фи O_n — це сімейство симетричних графів із високим непарним обхватом, визначених на деяких сімействах множин. Вони включають і узагальнюють графи Петерсена.

Визначення та приклади

Непарний граф O_n має одну вершину для кожної з (n − 1)-елементних підмножин множини з (2n — 1) елементів. Дві вершини пов'язані ребром тоді й лише тоді, якщо відповідні підмножини не перетинаються. Так, O_n — це граф Кнезера KG(2n − 1,n − 1), O₂ — трикутник, а O₃ — знайомий граф Петерсена.

Узага́льнені непа́рні гра́фи включають непарні графи і складані кубічні графи, і визначаються як дистанційно-регулярні графи з діаметром n − 1 і непарним обхватом 2n − 1 для деякого n.

Історія та застосування

Хоча графи Петерсена відомі від 1898 року, їх визначення як «непарних графів» датується роботою Ковальовскі, в якій він вивчає непарний граф O₄. Непарні графи вивчають з огляду на їх використання в хімічній теорії графів під час моделювання зсуву йонів вуглецю. Їх також використовують як мережеву топологію при паралельних обчисленнях.

Позначення O_n для цих графів запропонував 1972 року Норман Біггз. Біггз і Тоні Гардинер пояснюють назву непарних графів у неопублікованій монографії 1974 року — кожному ребру непарного графа можна зіставити єдиний елемент X, який є «odd man out» (що можна перекласти як «гравець без партнера виходить зі гри»), тобто елемент не належить жодній іншій підмножині, пов'язаній із вершинами, інцидентними даному ребру.

Властивості

Непарний граф 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.

Будь-який непарний граф 3-дуго-транзитивний — будь-який орієнтований триреберний шлях у непарному графі можна перевести в будь-який такий самий шлях за допомогою симетрії графа. Непарні графи дистанційно-транзитивні, оскільки вони дистанційно-регулярні. Як дистанційно-регулярні графи, вони однозначно визначаються своїм масивом перетинів — ніякий інший дистанційно-регулярний граф не може мати таких самих параметрів, що й непарний граф. Однак всупереч високому ступеню симетрії, непарні графи O_n для n > 2 ніколи не є графами Келі.

Непарні графи з n ≥ 3 мають обхват шість. Однак, хоча вони і не є двочастковими графами, їхні непарні цикли набагато довші, а саме непарний граф O_n має непарний обхват 2n − 1. Якщо n-регулярний граф має діаметр n − 1, непарний обхват 2n − 1 і тільки n різних власних значень, він повинен бути дистанційно-регулярним. Дистанційно-регулярні графи діаметра n − 1 і непарного обхвату 2n − 1 відомі як узага́льнені непа́рні гра́фи і включають складані кубічні графи так само, як і самі непарні графи.

Незалежні множини і розмальовка вершин

Нехай 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 максимальних незалежних множин.

Якщо I — максимальна незалежна множина, утворена множиною, яка містить елемент x, то доповнення множини I — це множина вершин, що не містять x. Це доповнення породжує парування в G. Кожна вершина незалежної множини суміжна n вершинам парування, а кожна вершина парування суміжна n − 1 вершинам незалежної множини. Зважаючи на цей розклад і з огляду на те, що непарні графи не є двочастковими, вони мають хроматичне число рівне трьом — вершинам максимальної незалежної множини можна призначити один колір, а два інших кольори отримаємо з парування, породженого доповненням.

Реберне розфарбування

За теоремою Візінга число кольорів, необхідних для розфарбування ребер непарного графа O_n, дорівнює або n, або n + 1, і у випадку графів Петерсена O₃ воно дорівнює n + 1. Якщо n — степінь двох, число вершин у графі непарне, звідки знову випливає, що число кольорів у реберному розфарбуванні дорівнює n + 1. Однак O₅, O₆ і O₇ можна розфарбувати n кольорами.

Біггз пояснює цю задачу такою історією: одинадцять футболістів у вигаданому місті Кроам хочуть утворити пари команд для міні-футболу (одна людина залишається судити зустріч) усіма 1386 різними способами і хочуть скласти розклад ігор між усіма парами, при цьому шість ігор кожної команди мають гратися в різні дні тижня, за відсутності ігор у неділю. Чи можливо це? У цій історії кожна гра представляє ребро O₆, всі дні представлені кольорами, а реберне розфарбування в 6 кольорів графа O₆ дає розклад.

Непарні графи і гамільтонові графи

Граф Петерсена O₃ — це добре відомий негамільтонів граф, але було показано, що графи від O₄ до O₁₄ містять гамільтонові цикли. Строгіше, комбінуючи задачу пошуку гамільтонових циклів і реберного розфарбування, можна розбити ребра графа O_n (для n = 4, 5, 6, 7) на найближче знизу ціле від (n/2) гамільтонових циклів. Якщо n непарне, решта ребер утворюють досконале поєднання. Для n = 8, непарне число вершин в O_n не дозволяє розфарбувати ребра у 8 кольорів, але не закриває можливості розкладання на чотири гамільтонових цикли.

Гіпотеза Ловаса про гамільтонів цикл припускає, що кожен непарний граф має гамільтонів шлях і що кожен непарний граф O_n з n ≥ 4 має гамільтонів цикл.

Література

• Norman Biggs. Second International Conference on Combinatorial Mathematics. — 1979. — Т. 319 (21 квітня). — С. 71—81. — DOI:10.1111/j.1749-6632.1979.tb32775.x.