Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A forest is a collection of trees.

Is there a similar notion for paths? e.g., a _______ is a collection of paths.

share|cite|improve this question
Not that I know of. You can call it a "path forest". – Yuval Filmus Feb 25 '14 at 0:44
I haven't heard of a suitable term either. Just to speculate wildly, I conjecture that it's because "tree" and "path" do not refer to the same sort of object. A tree is a type of graph (connected acyclic) and a forest is where we drop the acyclic part. A path, at the basic level, is a sort-of-ordered subset of the vertices/edges (depending on how you want to define it) of a graph, and we just overload the term to mean a graph that doesn't have any other vertices or edges either. Then with this view there's no "collection of paths", and by inertia we haven't created one since. – Luke Mathieson Feb 25 '14 at 0:51
@LukeMathieson I don't buy your argument that a path isn't a "real" graph at all. Paths are perfectly good graphs in their own right; the fact that their structure is so simple that they can be uniquely specified by listing their vertices in order doesn't affect that. – David Richerby Feb 25 '14 at 1:29
@DavidRicherby, I wasn't saying that they're not "real" graphs, I was speculating wildly about the historical reason we don't seem to have a neat, widely known term for disjoint union of paths. – Luke Mathieson Feb 25 '14 at 1:31
@LukeMathieson: You probably also meant that a forest is where you drop the condition of being connected. In any case, even if there are historical reasons why collections of paths were not given a name, surely by the time people started studying path covers this should not longer have been true. One could just as easily ask: Spanning Forest : Path cover :: Forest : ? – Niel de Beaudrap Feb 25 '14 at 6:14
up vote 5 down vote accepted

Wikipedia says that a graph all of whose non-trivial components are paths is a linear forest. Alternatively, you could call it just a disjoint union of paths.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.