Деревність графа

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

Приклад

Розбиття повного двочасткового графа ${\displaystyle K_{4,4}}$ на три ліси, що показує, що його деревність дорівнює трьом.

На малюнку показано повний двочастковий граф ${\displaystyle K_{4,4}}$ з розфарбованими в різні кольори розбиття графа на три ліси. ${\displaystyle K_{4,4}}$ не можна розбити на менше лісів, оскільки будь-який ліс на восьми вершинах має максимум сім ребер, тоді як весь граф має шістнадцять ребер, що більше, ніж подвоєне число ребер одного лісу. Отже, деревність графа ${\displaystyle K_{4,4}}$ дорівнює трьом.

Деревність як міра щільності

Деревність графа є мірою щільності графа — графи з великим числом ребер мають високу деревність, а графи з високою деревністю повинні мати щільні подграфи.

Точніше, оскільки будь-який ${\displaystyle n}$-вершинний ліс має не більше ${\displaystyle n-1}$ ребер, деревність графа з ${\displaystyle n}$ вершинами і ${\displaystyle m}$ ребрами не менша ${\displaystyle \lceil m/(n-1)\rceil }$. Крім того, підграфи будь-якого графа не можуть мати деревності, більшої за деревність самого графа, або, еквівалентно, деревність графа має бути не меншою за найбільшу деревність його підграфів. ^[en] довів, що ці два факти можна скомбінувати для характеризації деревності — якщо ${\displaystyle n_{S}}$ і ${\displaystyle m_{S}}$ позначають відповідно число вершин і ребер довільного підграфа ${\displaystyle S}$ даного графа, тоді деревність графа дорівнює ${\displaystyle \max\{\lceil m_{S}/(n_{S}-1)\rceil \}.}$

Будь-який планарний граф з ${\displaystyle n}$ вершинами має максимум ${\displaystyle 3n-6}$ ребер, звідки випливає формула Неша-Вільямса, що деревність планарного графа не перевищує трьох. Шнайдер використовував спеціальну декомпозицію планарного графа на три ліси, звану лісом Шнайдера, щоб знаходити вкладення у вигляді прямих відрізків будь-якого графа в решітку малої площі.

Алгоритми

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

Пов'язані концепції

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

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

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

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

Виродженість графа — це найбільше число, за всіма породженими підграфами графа, мінімуму степенів вершин підграфа. Виродженість графа з деревністю ${\displaystyle a}$ не менше ${\displaystyle a}$ і не більше ${\displaystyle 2a-1}$. Число розфарбування графа, відоме також як число Секереша — Вілфа, завжди дорівнює його виродженості плюс 1.

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

Дробова деревність — це вдосконалена деревність, визначена для графа ${\displaystyle G}$ як ${\displaystyle \max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.}$ Іншими словами, деревність графа — це стеля дробової деревності.

(a, b)-розкладаність узагальнює деревність. Граф є ${\displaystyle (a,b)}$-розкладаним, якщо його ребра можна розкласти на ${\displaystyle a+1}$ множин, кожна з яких дає ліс, за винятком однієї, яка дає граф з найбільшим степенем ${\displaystyle b}$. Граф із деревністю ${\displaystyle a}$ є ${\displaystyle (a,0)}$-розкладаним.

Примітки

1. Gabow, Westermann, 1992.
2. Szekeres, Wilf, 1968.
3. Jensen, Toft, 1995, с. 77f.

Література

• N. Alon. The linear arboricity of graphs // . — 1988. — Т. 62, вип. 3. — С. 311–325. — DOI:10.1007/BF02783300.
• B. Chen, M. Matsumoto, J. Wang, Z. Zhang, J. Zhang. A short proof of Nash-Williams' theorem for the arboricity of a graph // Graphs and Combinatorics. — 1994. — Т. 10, вип. 1. — С. 27–28. — DOI:10.1007/BF01202467.
• P. Erdős, A. Hajnal. On chromatic number of graphs and set-systems // . — 1966. — Т. 17, вип. 1–2. — С. 61–99. — DOI:10.1007/BF02020444.
• H. N. Gabow, H. H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications // . — 1992. — Т. 7, вип. 1. — С. 465–497. — DOI:10.1007/BF01758774.
• S. L. Hakimi, J. Mitchem, E. E. Schmeichel. Star arboricity of graphs // . — 1996. — Т. 149. — С. 93–98. — DOI:10.1016/0012-365X(94)00313-8.
• T. R. Jensen, B. Toft. Graph Coloring Problems. — New York : Wiley-Interscience, 1995. — .
• C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs // Journal of the London Mathematical Society. — 1961. — Т. 36, вип. 1. — С. 445–450. — DOI:10.1112/jlms/s1-36.1.445.
• C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests // Journal of the London Mathematical Society. — 1964. — Т. 39, вип. 1. — С. 12. — DOI:10.1112/jlms/s1-39.1.12.
• W. Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
• G. Szekeres, H. S. Wilf. An inequality for the chromatic number of a graph // . — 1968. — DOI:10.1016/s0021-9800(68)80081-x.
• W. T. Tutte. On the problem of decomposing a graph into n connected factors // Journal of the London Mathematical Society. — 1961. — Т. 36, вип. 1. — С. 221–230. — DOI:10.1112/jlms/s1-36.1.221.