In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
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
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
are where . Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
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
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...
of paths is called a
linear forest.
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 areas of mathematics, 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 mathem ...
, path graphs appear as the
Dynkin diagrams of type A. As such, they classify the
root system of type A and the
Weyl group of type A, which is the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
.
See also
*
Path (graph theory)
*
Caterpillar tree
*
Complete graph
*
Null graph
*
Path decomposition
*
Cycle (graph theory)
References
*
*
External links
*
{{interwiki extra, qid=Q1415372
Trees (graph theory)
Parametric families of graphs