Path (graph theory)

6-way graph

A path in a graph is a sequence of vertices in which each vertex is connected to the next edge.

Definitions

Let G be an undirected graph . A path in G is such a finite or infinite sequence of edges and vertices ^[1] $S=(...,a_{0},E_{0},a_{1},E_{1},...,E_{n-1},a_{n},...)$ ${\ displaystyle S = (..., a_ {0}, E_ {0}, a_ {1}, E_ {1}, ..., E_ {n-1}, a_ {n}, ...) }$ $S = (..., a_0,E_0, a_1, E_1, ..., E_{n-1}, a_n, ...)$ ,

that every two adjacent edges $E_{i-1}$ ${\ displaystyle E_ {i-1}}$ $E_{i-1}$ and $E_{i}$ ${\ displaystyle E_ {i}}$ $E_{i}$ have a common peak $a_{i}$ ${\ displaystyle a_ {i}}$ $a_{i}$ .

So you can write $...,E_{0}=(a_{0},a_{1}),E_{1}=(a_{1},a_{2}),...,E_{n}=(a_{n},a_{n+1}),...$ ${\ displaystyle ..., E_ {0} = (a_ {0}, a_ {1}), E_ {1} = (a_ {1}, a_ {2}), ..., E_ {n} = (a_ {n}, a_ {n + 1}), ...}$ $..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...$

Note that the same edge can occur several times along the way. If there are no edges preceding $E_{0}$ ${\ displaystyle E_ {0}}$ $E_{0}$ then $a_{0}$ ${\ displaystyle a_ {0}}$ $a_{0}$ is called the initial vertex S, and if there are no edges following $E_{(n-1)}$ ${\ displaystyle E _ {(n-1)}}$ $E_{(n-1)}$ then $a_{n}$ ${\ displaystyle a_ {n}}$ $a_n$ is called the final vertex S. Any vertex that belongs to two adjacent edges is called internal . Since edges and vertices in the path can be repeated, the inner vertex may turn out to be the start or end vertex.

If the starting and ending vertices coincide, the path is called cyclic . A path is called a chain , and a cyclic path is called a cycle if each of its edges occurs no more than once (vertices can be repeated). A non-cyclic chain is called a simple chain if no vertex is repeated in it. End cycle $a_{0}$ ${\ displaystyle a_ {0}}$ $a_{0}$ called a simple cycle if $a_{0}$ ${\ displaystyle a_ {0}}$ $a_{0}$ is not an intermediate vertex in it and no other vertices are repeated.

Unfortunately, this terminology is not well established. Wilson ^[2] wrote:

What we called the route is also called the path, the edge sequence.
A chain is called a path, a semi-simple path; a simple chain - a chain, a way, an arc, a simple way, an elementary chain; closed circuit - a cyclic chain, a circuit; cycle - by a contour, a contour chain, a simple cycle, an elementary cycle.
- ^[3] ^[4] ^[5]

Oriented cycle. Without arrows, it's just a cycle. This is not a simple cycle, since blue vertices are used twice.

Paths, chains, and loops are fundamental concepts in graph theory and are defined in the introductory part of most books on graph theory. See, for example, Bondi and Marty ^[6] , Gibbons ^[7] or Distel ^[8] .

Different kinds of paths

A path for which no edges of the graph connect two vertices of a path is called an induced path .

A simple chain containing all the vertices of a graph without repetition is known as the Hamiltonian path .

A simple cycle containing all the vertices of the graph without repetition is known as the Hamiltonian cycle .

The cycle obtained by adding the edge of the graph to the spanning tree of the original graph is known as the fundamental cycle.

Path Properties

Two paths are vertex independent if they do not have common internal vertices. Similarly, two paths are edge-independent if they do not have common inner edges.

The path length is the number of edges used in the path, while reusable edges are counted the corresponding number of times. The length can be zero if the path consists of only one vertex.

A weighted graph maps each edge to a value ( edge weight ). The weight of the path in a weighted graph is the sum of the weights of the edges of the path. Sometimes instead of the word weight , price or length is used .

Notes

↑ Ore, 2008 , 2.1 Routes, chains, and simple chains, p. 34-38.
↑ Wilson, 1977 , New Definitions, p. 37.
↑ Harari, 2003 , Routes and Connections, p. 232.
↑ Harari, 2003 , Digraphs and Connectivity., P. 232.
↑ Christofides, 1978 , Chapter 1. Introduction 2. Ways and routes, p. 13.
↑ Bondy, Murty, 1976 .
↑ Gibbons, 1985 .
↑ Distille, 2002 .

Literature

Harari F. Graph Theory. - M .: URSS , 2003 .-- 300 p. - ISBN 5-354-00301-6 .
Auray, Oystin . Graph theory. - M .: URSS , 2008 .-- 352 p. - ISBN 978-5-397-00044-4 .
N. Cristofides. Graph theory. Algorithmic approach. - 2nd .. - M .: Mir Publishing House, 1978.
R. Wilson. Introduction to graph theory. - M .: Mir Publishing House, 1977. - (Contemporary Mathematics. Introductory Courses).
JA Bondy, USR Murty. Graph Theory with Applications. - North Holland, 1976. - S. 12-21. - ISBN 0-444-19451-7 . Archived on April 13, 2010.
Reingard Distel. Graph theory. - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - ISBN 5-86134-101-X.
Gibbons, A. Algorithmic Graph Theory. - Cambridge University Press, 1985. - S. 5-6. - ISBN 0-521-28881-9 .
Bernhard Korte, László Lovász, Hans Jürgen Prömel Alexander Schrijver. Paths, Flows, and VLSI-Layout. - Algorithms and Combinatorics 9, Springer-Verlag, 1990. - ISBN 0-387-52685-4 .

Links

Weisstein, Eric W. Path Graph on Wolfram MathWorld .

[_0bd81af70326a442-1] Ore, 2008 , 2.1 Routes, chains, and simple chains, p. 34-38.

[_a3580cca2aafe41b-2] Wilson, 1977 , New Definitions, p. 37.

[_547cd857b9e17b56-3] Harari, 2003 , Routes and Connections, p. 232.

[_128a6417faa1a124-4] Harari, 2003 , Digraphs and Connectivity., P. 232.

[_2cd76b1349e76395-5] Christofides, 1978 , Chapter 1. Introduction 2. Ways and routes, p. 13.

[_b3962fc52d8df513-6] Bondy, Murty, 1976 .

[_47ff580344ca12e6-7] Gibbons, 1985 .

[_1bee45ca13232183-8] Distille, 2002 .