Edge (graph theory)

In graph theory , an edge denotes a part of a graph . An edge indicates whether two nodes are related to one another or whether they are connected in the graphical representation of the graph. In a directed graph an edge is an ordered pair of nodes, in an undirected graph an edge is a set of two nodes. Two nodes that are connected by an edge are called adjacent or adjacent.

Edge types and their notation

Unoriented edges

Edges in an undirected graph are called "undirected edges". An undirected edge is therefore a set of two nodes. Sometimes the term is also extended to directed graphs, to express that two nodes “a” and “b” are connected by both the edge and the edge . ${\displaystyle \left(a,b\right)}$ ${\displaystyle \left(b,a\right)}$

Directed edges

Edges in a directed graph are called "directed edges". In contrast to an undirected edge, it has an orientation. For an edge , the node is called the start node and the node is called the end node of the edge. A directed edge is also called an "arc" or an "arrow". Two edges , with and called "counter" or "antiparallel". ${\displaystyle e=\left(a,b\right)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{1}=\left(a,b\right)}$ ${\displaystyle e_{2}=\left(b,a\right)}$

Special edges

• Loop : Connects a knot to itself.
• Multiple edge / multi edge: Several edges of the same type run between two nodes in a multigraph . The individual edges are referred to as “parallel edges”.
• Multiple loop: A directed multiple edge in a multigraph that is also a loop.

Generalization: hyperedge

In hypergraphs , an edge can also connect more than two nodes as a so-called hyperedge .

literature

• Dénes Kőnig : Theory of finite and infinite graphs . Academic Publishing Company, Leipzig 1936.