Лінійна деревність

найменша кількість лінійних лісів, на які можна розбити граф

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

Нерозв'язана проблема математики:
Чи в будь-якого графа з найбільшим степенем лінійна деревність не перевищує ?
(більше нерозв'язаних проблем математики)

Лінійна деревність графа з найбільшим степенем завжди не менша від , оскільки кожен лінійний ліс може використовувати лише два з ребер вершини найбільшого степеня. Гіпотеза про лінійну деревність Акіями[en], Екзоо та Харарі[1] стверджує, що ця нижня межа точна. За цією гіпотезою будь-який граф має лінійну деревність, яка не перевищує [2]. Однак гіпотеза залишається недоведеною, і краща доведена верхня грань лінійної деревності дещо вища, з деякою сталою (за Фербером, Фоксом і Джейном[3]).

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

Лінійна деревність є варіацією деревності графа, найменшої кількості лісів, на які можна розбити ребра графа. Досліджувалась також лінійна k-деревність, варіант лінійної деревності, в якій будь-який шлях у лінійному лісі може мати не більше k ребер[4].

На відміну від деревності, яку можна встановити за поліноміальний час, задача встановлення лінійної деревності NP-складна. Навіть розпізнавання графів з лінійною деревністю два є NP-повною задачею[5]. Однак для кубічних графів та інших графів з найбільшим степенем три лінійна деревність завжди дорівнює двом, а розклад на два лінійні ліси можна знайти за лінійний час за допомогою алгоритму, заснованого на пошуку в глибину[6].

Примітки ред.

Література ред.