**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Path (graph theory)

Summary

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. , , or . cover more advanced algorithmic topics concerning paths in graphs.
A walk is a finite or infinite sequence of edges which joins a sequence of vertices.
Let G = (V, E, φ) be a graph. A finite walk is a sequence of edges (e1, e2, ..., en − 1) for which there is a sequence of vertices (v1, v2, ..., vn) such that φ(ei) = {vi, vi + 1} for i = 1, 2, ..., n − 1. (v1, v2, ..., vn) is the vertex sequence of the walk. The walk is closed if v1 = vn, and it is open otherwise. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or ray) has a first vertex but no last vertex.
A trail is a walk in which all edges are distinct.
A path is a trail in which all vertices (and therefore also all edges) are distinct.
If w = (e1, e2, ..., en − 1) is a finite walk with vertex sequence (v1, v2, ..., vn) then w is said to be a walk from v1 to vn. Similarly for a trail or a path. If there is a finite walk between two distinct vertices then there is also a finite trail and a finite path between them.
Some authors do not require that all vertices of a path be distinct and instead use the term simple path to refer to such a path where all vertices are distinct.
A weighted graph associates a value (weight) with every edge in the graph. The weight of a walk (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (32)

Related lectures (218)

Related concepts (16)

Related publications (175)

Related MOOCs (6)

Related units (4)

Related people (33)

Fundamental Groups

Explores fundamental groups, homotopy classes, and coverings in connected manifolds.

Properties of Trees: Nodes, Paths, and CyclesMOOC: Optimization: principles and algorithms - Linear optimization

Explores the properties of trees in graph theory, focusing on nodes, paths, cycles, and the characterization of trees in a directed graph.

Graph Theory: Path Weighted by Amplitude

Covers the calculation of paths in a graph, focusing on amplitude-weighted paths.

MATH-260(a): Discrete mathematics

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

PHYS-316: Statistical physics II

Introduction à la théorie des transitions de phase

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

K-vertex-connected graph

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected. A graph (other than a complete graph) has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Optimization: principles and algorithms - Linear optimization

Introduction to linear optimization, duality and the simplex algorithm.

Optimization: principles and algorithms - Linear optimization

Introduction to linear optimization, duality and the simplex algorithm.

Optimization: principles and algorithms - Network and discrete optimization

Introduction to network optimization and discrete optimization

Maximilien Claude Robert Dreveton

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all tem ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Water distribution systems (WDSs) are complex networks with numerous interconnected junctions and pipes. The robustness and reliability of these systems are critically dependent on their network structure, necessitating detailed analysis for proactive leak ...