Ліні́йна дере́вність неорієнтованого графа — це найменша кількість лінійних лісів, на які можна розбити граф. Тут лінійний ліс — це ациклічний граф із найбільшим степенем два, тобто диз'юнктне об'єднання шляхів.
Лінійна деревність графа з найбільшим степенем завжди не менша від , оскільки кожен лінійний ліс може використовувати лише два з ребер вершини найбільшого степеня. Гіпотеза про лінійну деревність , Екзоо та Харарі стверджує, що ця нижня межа точна. За цією гіпотезою будь-який граф має лінійну деревність, яка не перевищує . Однак гіпотеза залишається недоведеною, і краща доведена верхня грань лінійної деревності дещо вища, з деякою сталою (за Фербером, Фоксом і Джейном).
У регулярному графі лінійна деревність не може дорівнювати оскільки кінцеві точки будь-якого шляху в одному з лінійних лісів не можуть мати двох суміжних вершин, використаних у цьому лісі. Тому, для регулярних графів, з гіпотези про лінійну деревність випливає, що лінійна деревність точно дорівнює .
Лінійна деревність є варіацією деревності графа, найменшої кількості лісів, на які можна розбити ребра графа. Досліджувалась також лінійна -деревність, варіант лінійної деревності, в якій будь-який шлях у лінійному лісі може мати не більше ребер.
На відміну від деревності, яку можна встановити за поліноміальний час, задача встановлення лінійної деревності NP-складна. Навіть розпізнавання графів з лінійною деревністю два є NP-повною задачею. Однак для кубічних графів та інших графів з найбільшим степенем три лінійна деревність завжди дорівнює двом, а розклад на два лінійні ліси можна знайти за лінійний час за допомогою алгоритму, заснованого на пошуку в глибину.
Примітки
Література