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

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

Приклад

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

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

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

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

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

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

Алгоритми

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

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

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

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

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

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

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

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

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

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

Література

• N. Alon. The linear arboricity of graphs // Israel Journal of Mathematics. — 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 // Acta Mathematica Hungarica. — 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 // Algorithmica. — 1992. — Т. 7, вип. 1. — С. 465–497. — DOI:10.1007/BF01758774.
• S. L. Hakimi, J. Mitchem, E. E. Schmeichel. Star arboricity of graphs // Discrete Mathematics. — 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. — ISBN 0-471-02865-7.
• 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 // Journal of Combinatorial Theory. — 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.