In the
mathematical field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a path graph or linear graph is a
graph whose
vertices can be listed in the order such that the
edges are where . Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have
degree 1), while all others (if any) have degree 2.
Paths are often important in their role as
subgraphs of other graphs, in which case they are called
paths in that graph. A path is a particularly simple example of a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A
disjoint union of paths is called a
linear forest In graph theory, a branch of mathematics, a linear forest is a kind of forest formed from the disjoint union of path graphs. It is an undirected graph with no cycles in which every vertex has degree at most two. Linear forests are the same thin ...
.
Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See, for example, Bondy and Murty (1976), Gibbons (1985), or Diestel (2005).
As Dynkin diagrams
In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
, path graphs appear as the
Dynkin diagrams of type A. As such, they classify the
root system of type A and the
Weyl group
In mathematics, in particular the theory of Lie algebras, the Weyl group (named after Hermann Weyl) of a root system Φ is a subgroup of the isometry group of that root system. Specifically, it is the subgroup which is generated by reflections ...
of type A, which is the
symmetric group.
See also
*
Path (graph theory)
*
Caterpillar tree
*
Complete graph
*
Null graph
*
Path decomposition
*
Cycle (graph theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
A graph wit ...
References
*
*
External links
*
{{interwiki extra, qid=Q1415372
Trees (graph theory)
Parametric families of graphs