Древесность - Arboricity

В родословие из неориентированный граф это минимальное количество леса в которые его края могут быть разделенный. Эквивалентно это минимальное количество покрывающий леса необходимо покрыть все ребра графа. В Теорема Нэша-Вильямса обеспечивает необходимые и достаточные условия, когда граф k-арборический.

пример

Раздел полный двудольный граф K_4,4 на три леса, показывая, что он имеет три древовидности.

На рисунке показан полный двудольный граф K_4,4, причем цвета указывают на разделение его ребер на три леса. K_4,4 не может быть разделен на меньшее количество лесов, потому что любой лес в его восьми вершинах имеет не более семи ребер, в то время как весь граф имеет шестнадцать ребер, что более чем вдвое превышает количество ребер в одном лесу. Следовательно, древовидность K_4,4 это три.

Древовидность как мера плотности

Основная статья: Теорема Нэша-Вильямса

Древовидность графа - это мера того, насколько плотный граф таков: графы с большим количеством ребер имеют высокую древовидность, а графы с высокой древовидностью должны иметь плотный подграф.

Более подробно, поскольку любой n-вершинный лес имеет не более n-1 ребра, древесность графа с n вершинами и m ребрами не менее ${\displaystyle \lceil m/(n-1)\rceil }$. Кроме того, подграфы любого графа не могут иметь древовидность больше, чем сам граф, или, что то же самое, древовидность графа должна быть не меньше максимальной древовидности любого из его подграфов. Нэш-Вильямс доказал, что эти два факта можно объединить для характеристики древовидности: если мы положим n_S И м_S обозначим количество вершин и ребер соответственно любого подграфа S данного графа, то древовидность графа равна ${\displaystyle \max _{S}\{\lceil m_{S}/(n_{S}-1)\rceil \}.}$

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

Алгоритмы

Древовидность графа может быть выражена как частный случай более общего разделение матроидов задача, в которой желательно выразить набор элементов матроида как объединение небольшого числа независимых множеств. Как следствие, древовидность может быть вычислена с помощью полиномиального алгоритма (Габоу и Вестерманн 1992 ).

Связанные понятия

В анарборизм графа - это максимальное количество реберно-непересекающихся неациклических подграфов, на которые можно разбить ребра графа.

В звездное родословие графа - это размер минимального леса, каждое дерево которого является звезда (дерево с не более чем одним нелистовым узлом), на которое можно разбить ребра графа. Если дерево само по себе не является звездой, его звездообразность равна двум, что можно увидеть, разделив ребра на два подмножества на нечетных и четных расстояниях от корня дерева соответственно. Следовательно, древовидность любого графа по крайней мере равна древовидности и не более чем в два раза больше древовидности.

В линейная древовидность графа - это минимальное количество линейные леса (набор путей), на которые можно разбить ребра графа. Линейная древовидность графа тесно связана с его максимумом. степень и это номер откоса.

В псевдоарборичность графа - это минимальное количество псевдолеса на которые можно разделить его края. Эквивалентно, это максимальное отношение ребер к вершинам в любом подграфе графа, округленное до целого числа. Как и в случае с древовидностью, псевдоарборичность имеет матроидную структуру, позволяющую эффективно вычислять ее (Габоу и Вестерманн 1992 ).

В толщина графа - это минимальное количество плоских подграфов, на которые можно разбить его ребра. Поскольку любой планарный граф имеет древовидность три, толщина любого графа по крайней мере равна трети древовидности и не больше равна древовидности.

В вырождение графика является максимумом по всем индуцированные подграфы графика, минимального степень вершины в подграфе. Вырождение графа с древовидностью ${\displaystyle a}$ по крайней мере равно ${\displaystyle a}$, и не более чем равно ${\displaystyle 2a-1}$. Число раскраски графа, также известное как его число Секереса-Вильфа (Секерес и Вильф, 1968 г. ) всегда равно его вырожденности плюс 1 (Дженсен и Тофт 1995, п. 77f.).

В прочность графа - это дробное значение, целая часть которого дает максимальное количество непересекающихся остовных деревьев, которые могут быть нарисованы в графе. Проблема упаковки двойственна проблеме покрытия, возникающей из-за древовидности. Эти два параметра изучались вместе Тутте и Нэш-Вильямсом.

В фракционная древовидность является уточнением древовидности, как это определено для графа ${\displaystyle G}$ так как ${\displaystyle \max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.}$ Другими словами, древовидность графика - это потолок дробной древовидности.

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

В номер дерева - минимальное количество деревьев, покрывающих ребра графа.

Особые выступления

Древесность проявляется в Гипотеза Гольдберга – Сеймура.

Рекомендации

• Алон, Н. (1988). «Линейная древовидность графов». Израильский математический журнал. 62 (3): 311–325. Дои:10.1007 / BF02783300. Г-Н  0955135.
• Chen, B .; Matsumoto, M .; Wang, J .; Zhang, Z .; Чжан, Дж. (1994). «Краткое доказательство теоремы Нэша-Вильямса о древовидности графа». Графы и комбинаторика. 10 (1): 27–28. Дои:10.1007 / BF01202467. Г-Н  1273008.
• Эрдеш, П.; Хайнал, А. (1966). «О хроматическом числе графов и систем множеств» (PDF). Acta Mathematica Hungarica. 17 (1–2): 61–99. Дои:10.1007 / BF02020444. Г-Н  0193025. Архивировано из оригинал (PDF) на 2013-05-24. Получено 2011-05-30.
• Gabow, H.N .; Вестерманн, Х. Х. (1992). «Леса, фреймы и игры: алгоритмы математических сумм и приложений». Алгоритмика. 7 (1): 465–497. Дои:10.1007 / BF01758774. Г-Н  1154585.
• Хакими, С.Л.; Mitchem, J .; Шмейхель, Э. Э. (1996). «Звездная древность графов». Дискретная математика. 149: 93–98. Дои:10.1016 / 0012-365X (94) 00313-8. Г-Н  1375101.
• Jensen, T. R .; Тофт, Б. (1995). Проблемы с раскраской графиков. Нью-Йорк: Wiley-Interscience. ISBN  0-471-02865-7. Г-Н  1304254.
• К. Сент-Дж. А. Нэш-Уильямс (1961). «Реберно-непересекающиеся остовные деревья конечных графов». Журнал Лондонского математического общества. 36 (1): 445–450. Дои:10.1112 / jlms / s1-36.1.445. Г-Н  0133253.
• К. Сент-Дж. А. Нэш-Уильямс (1964). «Разложение конечных графов на леса». Журнал Лондонского математического общества. 39 (1): 12. Дои:10.1112 / jlms / s1-39.1.12. Г-Н  0161333.
• В. Шнайдер (1990). «Вложение плоских графов в сетку». Proc. 1-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA). С. 138–148.
• Секереш, Г.; Уилф, Х.С. (1968). «Неравенство для хроматического числа графа». Журнал комбинаторной теории. Дои:10.1016 / с0021-9800 (68) 80081-х. Г-Н  0218269.
• Тутте, В. Т. (1961). «К проблеме разложения графа на n связанных факторов». Журнал Лондонского математического общества. 36 (1): 221–230. Дои:10.1112 / jlms / s1-36.1.221. Г-Н  0140438.