Way (graph theory)

A graph that has a path with the nodes B, C, F and the sequence of edges D, {D, E}, E, {E, B}, B, {B, A}, A, {A, E}, E , {E, F}, F contains

In graph theory , path , path , edge train or edge sequence denotes a sequence of nodes in which two consecutive nodes are connected by an edge .

Definitions

path

A non-empty graph , with the set of nodes and the set of edges , is called a path if the nodes are different in pairs. For the sake of simplicity, a path is often given by the sequence of its nodes . It is important to note that the mirrored sequence also names this path. According to this definition, paths have no particular direction. The nodes and are called the end nodes of the path. Nodes that are not end nodes are also called inner nodes . ${\ displaystyle W}$ ${\ displaystyle \ {x_ {1}, x_ {2}, \ dotsc, x_ {n} \}}$ ${\ displaystyle \ {\ {x_ {1}, x_ {2} \}, \ {x_ {2}, x_ {3} \}, \ dotsc, \ {x_ {n-1}, x_ {n} \ } \}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {1}, x_ {2}, \ dotsc, x_ {n}}$ ${\ displaystyle x_ {n}, x_ {n-1}, \ dotsc, x_ {1}}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {n}}$

In linguistic usage one often says that a graph contains a path. That should mean that this path is a subgraph of the graph. Depending on the context, the term path can be adapted. In the directed graph , for example, all successive nodes and by a directed edge to be connected, so that the path also indicating a direction. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {i + 1}}$ ${\ displaystyle (x_ {i}, x_ {i + 1})}$

The term “way” is not used consistently in the literature. The definition given essentially follows the books by Diestel and Lovász . In unambiguous contexts - and especially in the case of simple graphs - in the graph-theoretical specialist literature, a path is also given directly via the sequence of neighboring nodes, as in Aigner and Kőnig . Occasionally the term path is also used for a way (Steger), probably because in the English-language literature way is referred to as a path , but sometimes also as a simple path .

A path in which the starting and ending nodes are identical is called a cycle and if this is the only repeated node in the sequence of nodes, this is called a circle .

Edge pull, edge sequence, path

In a (directed) graph is called a sequence , in the nodes and edges of the graph are alternated and for which it holds that for the edge of the mold has an edge sequence of the graph. Furthermore, edges and nodes can be repeated within an edge segment. An edge from to implies the existence of a path with the end nodes and . Edge trains in which the first and last nodes match are called closed . ${\ displaystyle x_ {1}, e_ {1}, x_ {2}, e_ {2}, \ dotsc, e_ {n-1}, x_ {n}}$ ${\ displaystyle i = 1, \ dotsc, n-1}$ ${\ displaystyle e_ {i}}$ ${\ displaystyle \ {x_ {i}, x_ {i + 1} \}}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {n}}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {n}}$

Of particular interest are those edge trains that are closed and in which each edge of the graph occurs exactly once. Such an edge train is called Eulerian after Leonhard Euler or simply an Eulerian train or also an Eulerian line . The existence of such was investigated by Euler in connection with the solution of the Königsberg bridge problem (1736), which is considered one of the initial problems of graph theory.

The term of the edge train is also not used uniformly in the specialist literature. The definition given here is based on the books by Diestel and Lovász et al. a. Aigner and Kőnig, on the other hand, speak of edge sequences in their books . Kőnig uses the term edge train to make it clear that no edges are repeated. Sometimes the term way is also used for edge pull (Steger). The term is not used uniformly in English-language literature either; it is sometimes referred to as walk , but sometimes also referred to as path .

With Rudolf Halin , an edge sequence (in the local sense), in which no node and no edge occur more than once, is also referred to as an edge train or, for a shorter time, as a path for directed graphs . Horst Sachs, on the other hand, calls such an elementary path .

A - B way, v - w way, a - B way

If and are subsets of the vertex set of a graph, then a path is called a - path if one of its end nodes is in and the other is in . Instead of a - -way one also speaks of a - -way . A set of - -paths is called a - -fan if the pairs of paths only have one node in common. ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle V}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle \ {v \}}$ ${\ displaystyle \ {w \}}$ ${\ displaystyle v}$ ${\ displaystyle w}$ ${\ displaystyle a}$ ${\ displaystyle B}$ ${\ displaystyle a}$ ${\ displaystyle B}$ ${\ displaystyle a}$

Disjoint ways

Two paths and in a graph are called free of crossings , vertex disjoint or just disjoint , if there is no pair with out and out , for that is, they have no inner nodes in common. ${\ displaystyle W_ {1} = v_ {1}, \ dotsc, v_ {k}}$ ${\ displaystyle W_ {2} = u_ {1}, \ dotsc, u_ {l}}$ ${\ displaystyle (i, j)}$ ${\ displaystyle i}$ ${\ displaystyle \ {2, \ dotsc, k-1 \}}$ ${\ displaystyle j}$ ${\ displaystyle \ {2, \ dotsc, l-1 \}}$ ${\ displaystyle v_ {i} = u_ {j}}$

A set of paths is called free of intersection , node disjoint or disjoint if the paths are pairwise disjoint.

A set of disjoint paths in a graph with the property that every node of the graph lies on one of these paths is called path coverage of the graph.

Length and distance

In graphs without weights on the edges , the length of a path or line of edges denotes the number of edges. In edge-weighted graphs, the length of a path is the sum of the edge weights of all associated edges. The length of the longest path in a graph is called the perimeter of the graph.

A shortest path from a node to a node in a graph is a path from to whose length is minimal. The length of a shortest path is then called spacing or distance of after . The eccentricity of a node is the maximum distance to all other nodes in the graph. The edge of a graph is the set of nodes with maximum eccentricity. Note that in directed graphs, the distance depends on the direction of the path. In particular, it can be that a directed path only exists in one direction. ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle t}$

The greatest distance between two nodes in a graph is called the diameter of the graph. The diameter is the maximum of all eccentricities of the nodes in . The radius of a graph is the minimum of the eccentricities of its nodes. The following applies to all graphs ${\ displaystyle G}$ ${\ displaystyle D (G)}$ ${\ displaystyle G}$ ${\ displaystyle R (G)}$ ${\ displaystyle G}$

{\ displaystyle R (G) \ leq D (G) \ leq 2 \ cdot R (G)}

.

The nodes, whose eccentricity corresponds to the radius, form the center of the graph.

Distance graph

The distance graph to a graph describes the complete (i.e. every two nodes are connected by an edge, possibly in directed graphs in both directions, but there are no loops) edge-weighted graph on the node set , of which each edge is the distance as the edge weight between the two nodes in maps. ${\ displaystyle G = (V, E)}$ ${\ displaystyle V}$ ${\ displaystyle G}$

literature

Reinhard Diestel : graph theory . 3rd, revised and expanded edition. Springer Verlag, Berlin / Heidelberg / New York (and others) 2006, ISBN 978-3-540-21391-8 .

Rudolf Halin: Graph Theory I (= yields of research . Volume 138 ). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 ( MR0586234 ).

Dénes König : Theory of finite and infinite graphs . With a treatise by L. Euler. Ed .: H. Sachs (= Teubner Archive for Mathematics . Volume 6 ). BSB BG Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4 .

Horst Sachs: Introduction to the theory of finite graphs . Carl Hanser Verlag, Munich 1971, ISBN 3-446-11463-7 ( MR0345857 ).

Klaus Wagner : Theory of graphs (= BI university pocket books. 248 / 248a). Bibliographisches Institut, Mannheim ( inter alia ) 1970, ISBN 3-411-00248-4 ( MR0282850 ).

Individual evidence

↑ ^a ^b Reinhard Diestel: Graph Theory , 3rd, revised. and exp. Edition, Springer, Berlin, 2006, ISBN 3-540-21391-0 , p. 7ff.
↑ ^a ^b László Lovász, Jósef Pelikán, Katalin Vesztergombi: Discrete Mathematics . Springer, Berlin, 2003, ISBN 0-387-95584-4 , pp. 163ff.
↑ ^a ^b Martin Aigner: Diskrete Mathematik , 6., corr. Edition, Vieweg, 2006, ISBN 3-8348-0084-8 .
↑ ^a ^b ^c Dénes Kőnig: Theory of finite and infinite graphs . Academic Publishing Company, Leipzig 1936.
↑ ^a ^b Angelika Steger: Discrete Structures , 2nd Edition, Volume 1: Kombinatorik, Graphentheorie, Algebra, Springer, Berlin, 2007, ISBN 978-3-540-46660-4 , p. 61.
↑ Kőnig, op.cit., P. 35
^ Rudolf Halin: Graphentheorie I. 1980, p. 18
^ Rudolf Halin: Graphentheorie I. 1980, p. 19
↑ Horst Sachs: Introduction to the theory of finite graphs. 1971, pp. 118-121

[diestel-1] Reinhard Diestel: Graph Theory , 3rd, revised. and exp. Edition, Springer, Berlin, 2006, ISBN 3-540-21391-0 , p. 7ff.

[lovasz-2] László Lovász, Jósef Pelikán, Katalin Vesztergombi: Discrete Mathematics . Springer, Berlin, 2003, ISBN 0-387-95584-4 , pp. 163ff.

[aigner-3] Martin Aigner: Diskrete Mathematik , 6., corr. Edition, Vieweg, 2006, ISBN 3-8348-0084-8 .

[könig-4] Dénes Kőnig: Theory of finite and infinite graphs . Academic Publishing Company, Leipzig 1936.

[steger-5] Angelika Steger: Discrete Structures , 2nd Edition, Volume 1: Kombinatorik, Graphentheorie, Algebra, Springer, Berlin, 2007, ISBN 978-3-540-46660-4 , p. 61.

[könig-1-6] Kőnig, op.cit., P. 35

[RH-Ia-7] Rudolf Halin: Graphentheorie I. 1980, p. 18

[RH-Ib-8] Rudolf Halin: Graphentheorie I. 1980, p. 19

[HS-I-9] Horst Sachs: Introduction to the theory of finite graphs. 1971, pp. 118-121