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

Дробове розфарбування — поняття в молодій галузі теорії графів, відомій як теорія дробових графів. Дробове розфарбування є узагальненням звичайного розфарбування. У традиційному розфарбуванні графа кожній вершині призначається певний колір, і суміжним вершинам — пов'язаним ребрами, — має бути призначено різні кольори. У дробовому розфарбуванні кожній вершині призначається набір кольорів. Обмеження, що накладаються на суміжні вершини, залишаються в силі, тому якщо дві вершини з'єднано ребром, вони не повинні мати спільних кольорів.

5:2-розфарбування графа додекаедра. A 4:2–розфарбування цього графа не існує.

Дробове розфарбування графа можна розглядати як ^[en] традиційного розфарбування графа. Навіть більше, з погляду лінійного програмування задача дробового розфарбування значно простіша, ніж задача традиційного розфарбування.

Визначення

Вгорі: 3:1-розфарбування циклу з 5 вершин, і відповідне 6:2-розфарбування. Внизу: 5:2-розфарбування того ж графа.

b-Кратне розфарбування графа ${\displaystyle G}$ — призначення наборів із ${\displaystyle b}$ кольорів вершинам графа так, що суміжні вершини не мають спільних кольорів.

a:b-Розфарбування — ${\displaystyle b}$-кратне розфарбування, що містить у цілому ${\displaystyle a}$ кольорів.

b-Кратне хроматичне число ${\displaystyle \chi _{b}(G)}$ — найменше ${\displaystyle a}$, за якого існує ${\displaystyle a:b}$-розфарбування.

Дробовим хроматичним числом ${\displaystyle \chi _{f}(G)}$ називають

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$

Зауважимо, що границя існує, оскільки ${\displaystyle \chi _{b}(G)}$ а^[en], тобто, ${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G)}$.

Дробне хроматичне число можна визначити в термінах теорії ймовірності. ${\displaystyle \chi _{f}(G)}$ — це найменше ${\displaystyle k}$, для якого існує розподіл імовірності на незалежних множинах графа ${\displaystyle G}$ такий, що для будь-якої вершини ${\displaystyle v}$ та незалежної множини ${\displaystyle S}$

${\displaystyle \Pr(v\in S)\geq {\frac {1}{k}}}$.

Деякі властивості ${\displaystyle \chi _{f}(G)}$:

${\displaystyle \chi _{f}(G)\geq n(G)/\alpha (G)}$

і

${\displaystyle \omega (G)\leq \chi _{f}(G)\leq \chi (G)}$.

Тут ${\displaystyle n(G)}$ — порядок графа ${\displaystyle G}$, ${\displaystyle \alpha (G)}$ — число незалежності, ${\displaystyle \omega (G)}$ — клікове число, а ${\displaystyle \chi (G)}$ — хроматичне число.

Дробове хроматичне число в термінах лінійного програмування

Дробне хроматичне число ${\displaystyle \chi _{f}(G)}$ графа ${\displaystyle G}$ можна знайти, розв'язавши задачу лінійного програмування. Нехай ${\displaystyle {\mathcal {I}}(G)}$ — набір усіх незалежних множин графа ${\displaystyle G}$, і нехай ${\displaystyle {\mathcal {I}}(G,x)}$ — усі ті незалежні множини, які включають вершину ${\displaystyle x}$. Для кожної незалежної множини ${\displaystyle I}$ визначимо невід'ємну дійсну змінну ${\displaystyle x_{I}}$. Тоді ${\displaystyle \chi _{f}(G)}$ це найменше значення функції

${\displaystyle \sum _{I\in {\mathcal {I}}(G)}x_{I}}$,

за обмежень ${\displaystyle \sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1}$ для кожної вершини ${\displaystyle x}$.

Двоїста задача цій задачі лінійного програмування обчислює «дробове кликове число», послаблення до дробових чисел цілочисельної концепції клікового числа. Отже, для вершин графа ${\displaystyle G}$ можна ввести вагу, за якої сумарна вага будь-якої незалежної множини не перевищує 1. За теоремою про сильну двоїстість задач лінійного програмування оптимальні розв'язки обох задач збігаються. Зауважимо, однак, що обидві задачі мають розмір, що експоненційно залежить від числа вершин графа G, так що обчислення дробового хроматичного числа графа є NP-складною задачею. Це контрастує із задачею дробового реберного розфарбування графа, яке можна знайти за поліноміальний час, що є прямим наслідком теореми Едмондса.

Застосування

Дробове розфарбування графа використовують у календарному плануванні. У цьому випадку граф ${\displaystyle G}$ є графом конфліктів — ребро ${\displaystyle G}$ між вершинами ${\displaystyle u}$ і ${\displaystyle v}$ означає неможливість виконання ${\displaystyle u}$ і ${\displaystyle v}$ одночасно. Тоді роботи, які виконуються одночасно, мають бути незалежною множиною у графі ${\displaystyle G}$.

Оптимальне дробове розфарбування ${\displaystyle G}$ тоді забезпечує розклад із найменшим загальним часом, у якому будь-яка вершина (робота) виконується (принаймні) один раз і в будь-який момент часу активні вершини утворюють незалежну множину. Якщо знайдено розв'язок ${\displaystyle x}$ задачі лінійного програмування, описаної вище, слід просто пройти всі незалежні множини ${\displaystyle I}$ в довільному порядку. Для кожного ${\displaystyle I}$ роботи з неї виконуватимуться протягом ${\displaystyle x_{I}}$ проміжків часу. В решту часу роботи з ${\displaystyle I}$ не виконуватимуться.

Конкретніший приклад. Нехай кожна вершина графа ${\displaystyle G}$ — радіопередавач у бездротовій мережі. Тоді можна ребра ${\displaystyle G}$ подати як інтерференцію радіопередавачів. Кожен із радіопередавачів має в цілому працювати одну одиницю часу. Оптимальне дробове розфарбування забезпечує найменший за часом розклад (тобто розклад максимальної пропускної спроможності) без конфліктів.

Порівняння з традиційним розфарбуванням графа

Якщо є вимога, що вершина повинна працювати безперервно, без перемикань, то традиційне розфарбування графа дає оптимальний розклад: спочатку протягом одиниці часу працюють вершини з першим кольором, потім вершини кольору 2, і т. д. Знову в кожний момент часу вершини, що працюють, утворюють незалежну множину.

Як правило, дробове розфарбування графа дає коротший розклад, ніж звичайне. Але цей розклад виходить коротшим за рахунок увімкнення/вимкнення пристроїв (таких як радіопередавачі) більше одного разу.

Примітки

1. ^[en] and Mihalis Yannakakis: «On the hardness of approximating minimization problems», J. ACM 41:5(1994), p. 960—981.
2. Bruce Hajek and Galen Sasaki: «Link scheduling in polynomial time», IEEE Transactions on Information Theory 34:5(1988), p. 910—917.
3. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. — Berlin; Heidelberg; New York, N.Y. : Springer-Verlag, 2003. — С. 474. — .

Посилання

• Edward R. Scheinerman, Daniel H. Ullman. Fractional graph theory. — New York : Wiley-Interscience, 1997. — .
• Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — .