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

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

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

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

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

Властивості Непарний граф On є регулярним графом степеня n. Він має вершин і ребер. Таким чином, число вершин для n = 1, 2, … буде

1, 3, 10, 35, 126, 462, 1716, 6435 ().

Дистанція і симетрія Якщо дві вершини в On відповідають множинам однакового розміру, що відрізняються k елементами, то можна отримати з першої другу за 2k кроків, на кожному кроці прибираючи або додаючи один елемент. Якщо 2k < n, то це найкоротший шлях. В іншому випадку можна знайти коротший шлях цього типу, якщо почати з доповняльної до другої множини, а потім отримати другу множину, зробивши ще один крок. Таким чином, діаметр графа On дорівнює n − 1.

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

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

Незалежні множини і розмальовка вершин Нехай On — непарний граф, визначений на (2n − 1)-елементних підмножинах множини X, і нехай x — елементи множини X. Тоді серед вершин On рівно вершин відповідають множинам, які містять x. Оскільки всі ці множини містять x, вони не є неперетинними, і утворюють незалежну множину графа On. Таким чином, On має 2n − 1 різних незалежних множин розміру . Із випливає, що це максимальні незалежні множини графа On. Таким чином, число незалежності графа On дорівнює Більш того, будь-яка максимальна незалежна множина повинна мати такий вигляд, так що On має рівно 2n − 1 максимальних незалежних множин.

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

Реберне розфарбування За теоремою Візінга число кольорів, необхідних для розфарбування ребер непарного графа On, дорівнює або n, або n + 1, і у випадку графів Петерсена O3 воно дорівнює n + 1. Якщо n — степінь двох, число вершин у графі непарне, звідки знову випливає, що число кольорів у реберному розфарбуванні дорівнює n + 1. Однак O5, O6 і O7 можна розфарбувати n кольорами.

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

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

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

Примітки

Література