Talk:Arboricity
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Recent redefinition by Phaunt[edit]
Phaunt (talk · contribs) changed the lede sentence to read "The arboricity of an undirected graph is the size of the minimum forest into which its edges can be partitioned." I believe it is wrong in multiple ways, so I reverted, but it may be worth more discussion here.
- First, if a graph has cycles, its edges cannot be partitioned into a single forest. A forest is a single graph with no cycles, or equivalently the disjoint union of trees. If one partitions the edges of a cyclic graph into disjoint trees, the trees are not disjoint, so it is not a forest.
- Second, the "size" of a forest is unclear and it is not obvious that it refers to the number of trees.
- Third, the number of trees into which the edges of a graph can be partitioned is not the same as arboricity. Consider, e.g., a dumbell graph formed by two cycles connected by a single bridge edge. Its arboricity is two (it is easy to partition the edges into two forests: just make one forest consist of an edge from each cycle, and the other forest consist of all the rest of the edges) but if one tries to partition its edges into trees, three trees are required.
—David Eppstein 03:15, 15 August 2007 (UTC)
The example picture seems incorrect. The middle green edge is disconnected and should actually be blue. — Preceding unsigned comment added by 193.43.246.250 (talk • contribs)
- No, it's correct. For arboricity, the problem is to partition the edges of the graph into forests; they don't have to be connected. Partitioning the edges into connected trees (that might not span all the vertices) is a different and much harder problem. —David Eppstein (talk) 15:50, 27 May 2014 (UTC)