Linear arboricity (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Rhombic_dodecahedron_linear_arboricity.svg?width=300 |
| dbo:wikiPageID | 36344163 (xsd:integer) |
| dbo:wikiPageLength | 6880 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032106138 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Arboricity dbr:Path_graph dbr:Regular_graph dbr:Cubic_graph dbr:Undirected_graph dbr:Upper_bound dbr:Degree_(graph_theory) dbr:Depth-first_search dbc:Graph_invariants dbr:NP-complete dbr:NP-hard dbr:Linear_time dbr:Lower_bound dbr:Hamiltonian_decomposition dbr:Linear_forest dbr:Graph_theory dbr:Disjoint_union dbr:Polynomial_time dbr:Hamiltonian_cycle dbr:File:Rhombic_dodecahedron_linear_arboricity.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Mvar dbt:R dbt:Reflist dbt:Unsolved |
| dct:subject | dbc:Graph_invariants |
| 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) |
| rdfs:label | Linear arboricity (en) Линейная древесность (ru) |
| owl:sameAs | yago-res:Linear arboricity wikidata:Linear arboricity dbpedia-hu:Linear arboricity dbpedia-ru:Linear arboricity https://global.dbpedia.org/id/2Nr63 |
| prov:wasDerivedFrom | wikipedia-en:Linear_arboricity?oldid=1032106138&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Rhombic_dodecahedron_linear_arboricity.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Linear_arboricity |
| is dbo:wikiPageRedirects of | dbr:Linear_arboricity_conjecture |
| is dbo:wikiPageWikiLink of | dbr:Arboricity dbr:Slope_number dbr:Hamiltonian_decomposition dbr:Linear_arboricity_conjecture dbr:Linear_forest dbr:Edge_coloring dbr:List_of_unsolved_problems_in_mathematics |
| is foaf:primaryTopic of | wikipedia-en:Linear_arboricity |
