Path (graph theory)

In graph theory, path, path, or augmenting path edge sequence refers to a sequence of nodes in which any two consecutive nodes are connected by an edge.

Definitions

Way

A non-empty graph W, the vertex set and the edge set is called path if the nodes are pairwise different. Often a way for the sake of simplicity by the sequence of its nodes is specified. Here, it is to note that the mirrored sequence identifies that route. According to this definition have no way distinguished direction. The nodes and is called the end nodes of the path. Nodes which are not end nodes are also called inner node.

In language use the term is often used, a graph contains a path W. Thus one refers to the fact that the path W is a subgraph of the graph. Depending on the context, you can adjust the term way, for example, for directed graphs. Here all consecutive nodes must be connected through a directed edge. In this case, a path is always also a direction.

The notion of path is not used consistently in the literature. This definition will follow the books of Diestel and Lovász, inter alia Sometimes a path directly through the sequence of incident nodes pairwise different is specified (see Aigner and Kőnig ). In this case, the route has claimed an implied direction. Occasionally, the term path is used for a path ( Steger ), probably because in the English literature as a way path, but partly also as a simple path is called.

A way in which the start to the end node is identical, and this is repeated, the only node in the node string is called cycle or circuit.

Augmenting path and sequence of edges

In a graph is called a sequence in which nodes and edges of the graph alternately and for which it holds that for the edge has the form, a 'augmenting the graph. Unlike edge trains ways to own an implied orientation. Furthermore, it may repeat edges and nodes within an edge train. An augmenting path from to implies the existence of a path to the end node and. Closed edges trains in which the first and the last node hot match.

Of particular interest is closed edges trains in which all edges are included exactly once. Such edges moves are called Euler tour (sometimes Eulerzug ), their existence has already been studied by Leonard Euler in connection with the Königsberg bridge problem, which is regarded as one of the first problems in the field of graph theory.

Also, the term 'augmenting path is not used consistently in the literature. The definition given here is based on the books by Diestel and Lovász, inter alia, Aigner and Kőnig speak in their books, however, of edge sequences. Kőnig uses the term 'augmenting to make it clear that no edges are repeated. It is sometimes also the term for 'augmenting path used ( Steger ). Even in the English literature, the term is not used consistently, it is sometimes referred to walk, but sometimes referred to as path.

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

Are and subsets of the node set of a graph, so is referred to as a path - way, if one of its end nodes is in and the other in. Instead of one - way one speaks also of a - way. A lot of - paths is called a - fan when the paths in pairs have only the nodes together.

Disjoint paths

Two-way and in a graph called crossing-free, node-disjoint or just disjoint if there is no pair with out and out, for that is so they have no internal nodes together.

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

A set of disjoint paths in a graph having the property that each node of the graph is located on one of these paths is path cover of the graph.

Length and distance

In graphs without weights on the edges refers to the length of a road or the number of edge coating of its edges. In edge-weighted graph is defined as the length of a path, the sum of the edge weights of all the associated edges. The length of the longest path in a graph is called the circumference of the graph.

As a shortest path from a node to a node in a graph referred to by a way of which the length is minimal. The length of a shortest path is then called distance or distance from to. The eccentricity of a node is the maximum distance to all other nodes of the graph. The edge of the graphene is the set of nodes with a maximum eccentricity. Note that, in the directed graph, the distance depending on the direction of the path. In particular, it may be that only in one direction, there is a directed path.

The greatest distance between two nodes in a graph is called the diameter of the graph. The diameter is thus the maximum of all the eccentricities of the nodes in. The radius of the graph is the minimum of the eccentricity of its nodes. For all graphs

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

Distance graph

The distance graph to a graph is the complete ( that is, any two vertices are connected by an edge, if necessary, in a directed graph in both directions with it but no loops are ) edge-weighted graph on the node set of each edge as an edge weight of the distance between the two nodes in associates.