| dbo:abstract
|
- In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned into. Here, a linear forest is an acyclic graph with maximum degree two; that is, it is a disjoint union of path graphs. Linear arboricity is a variant of arboricity, the minimum number of forests into which the edges can be partitioned. The linear arboricity of any graph of maximum degree is known to be at least and is conjectured to be at most . This conjecture would determine the linear arboricity exactly for graphs of odd degree, as in that case both expressions are equal. For graphs of even degree it would imply that the linear arboricity must be one of only two possible values, but determining the exact value among these two choices is NP-complete. (en)
- Линейная древесность неориентированного графа — это наименьшее число линейных лесов, на которые может быть разбит граф. Здесь линейный лес — это ациклический граф с максимальной степенью два, то есть дизъюнктное объединение путей. Нерешённые проблемы математики: Любой граф с максимальной степенью имеет линейную древесность, не превосходящую ? Линейная древесность графа с максимальной степенью всегда не меньше , поскольку каждый линейный лес может использовать только два из рёбер вершины максимальной степени. Гипотеза о линейной древесности Акиямы, Экзоо и Харари утверждает, чта это нижняя граница точна. Согласно этой гипотезе любой граф имеет линейную древесность, не превосходящую . Однако гипотеза остаётся недоказанной, и лучшая доказанная верхняя грань линейной древесности несколько выше, с некоторой константой (согласно Ферберу, Фоксу и Джейну). В регулярном графе линейная древесность не может быть равна , поскольку конечные точки любого пути в одном из линейных лесов не могут иметь две смежные вершины, использованные в этом лесе. Поэтому, для регулярных графов, из гипотезы о линейной древесности следует, что линейная древесность в точности равна . Линейная древесность является вариацией древесности графа, минимального числа лесов, на которые могут быть разбиты рёбра графа. Исследовалась также линейная k-древесность, вариант линейной древесности, в которой любой путь в линейном лесе может иметь не более k рёбер. В отличие от древесности, которая может быть установлена за полиномиальное время, задача установления линейной древесности NP-трудна. Даже распознавание графов с линейной древесностью два является NP-полной задачей. Однако для кубических графов и других графов с максимальной степенью три линейная древесность всегда равна двум, а разложение на два линейных леса может быть найдено за линейное время с помощью алгоритма, основанного на поиске в глубину. (ru)
|
| rdfs:comment
|
- In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned into. Here, a linear forest is an acyclic graph with maximum degree two; that is, it is a disjoint union of path graphs. Linear arboricity is a variant of arboricity, the minimum number of forests into which the edges can be partitioned. (en)
- Линейная древесность неориентированного графа — это наименьшее число линейных лесов, на которые может быть разбит граф. Здесь линейный лес — это ациклический граф с максимальной степенью два, то есть дизъюнктное объединение путей. Нерешённые проблемы математики: Любой граф с максимальной степенью имеет линейную древесность, не превосходящую ? (ru)
|
