Edge Sequence

graph-theory

Definition

Edge Sequence

Undirected: A sequence of edges $e_1,e_2,\dots ,e_k\in E(G)$ of an undirected graph $G$ is called edge sequence if there exist vertices $v,v_1,v_2,\dots ,v_{k-1},w\in V(G)$ with:

$$e_1=v{v}_1,e_2=v_1{v}_2,\dots ,e_{k-1}=v_{k-2}{v}_{k-1},e_k=v_{k-1}w$$

where the vertices can be traversed from $v$ to $w$ in any order.

Directed: A sequence of edges $e_1,e_2,\dots ,e_k\in E(G)$ of a directed graph $G$ is called edge sequence if, for any two consecutive edges $e_j,e_{j+1}$ ($1\le j\le k$), the end node of $e_j$ matches the start node of $e_{j+1}$. That is, there exists nodes $v,v_1,v_2,\dots ,v_{k-1},w$ sucht that:

$$e_1=(v,v_1),e_2=(v_1,v_2),\dots ,e_{k-1}=(v_{k-2},v_{k-1}),e_k=(v_{k-1},w)$$

Empty Edge Sequence

Empty Edge Sequence

An edge sequence of length $0$ is called empty edge sequence and does not contain any edges .

Kantenzug

todo

Kantenzug

A Kantenzug is an edge sequence where all edges $e_j$ are different, meaning each edges is only traversed once.

Path

Weg, Pfad, Bahn

Definition

Path

A path is an edge sequence where each vertex is only visited once.

Link to original

Loop

Kreis

Loop

An edge sequence is called loop if all vertices except $v$ are start and end nodes, different and and each edge only occurrs once.