Basic graph definitions

Directed and undirected graphs

1. A directed graph [math]\displaystyle{ G=(V,A) }[/math] consists of a finite set [math]\displaystyle{ V }[/math] of nodes (a.k.a. vertices) and a multiset [math]\displaystyle{ A }[/math] of ordered pairs of nodes. The elements of [math]\displaystyle{ A }[/math] are the arcs of [math]\displaystyle{ G }[/math].
2. An undirected graph [math]\displaystyle{ G=(V,E) }[/math] consists of a finite set [math]\displaystyle{ V }[/math] of nodes (a.k.a. vertices) and a multiset [math]\displaystyle{ E }[/math] of unordered pairs of nodes, the edges of [math]\displaystyle{ G }[/math].
3. A directed or undirected graph is simple, if:
   1. No node is paired with itself in [math]\displaystyle{ A }[/math] and [math]\displaystyle{ E }[/math], respectively.
   2. The multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ E }[/math], respectively, are sets.
4. A directed graph [math]\displaystyle{ G=(V,A) }[/math] is symmetric if [math]\displaystyle{ (v,w)\in A }[/math] implies [math]\displaystyle{ (w,v)\in A }[/math], and anti-symmetric if [math]\displaystyle{ (v,w)\in A }[/math] implies [math]\displaystyle{ (w,v)\not\in A }[/math].

Adjacency, incidence, and degree

1. Two nodes of a directed or undirected graph are called adjacent if they share at least one arc/edge.
2. A node and an arc/edge are called incident if the node belongs to the arc/edge.
3. Two arcs/edges are called incident if they share at least one node.
4. For a node, the number of incident arcs/edges is the degree of this node.
5. Consider a directed graph [math]\displaystyle{ G=(V,A) }[/math] and a node [math]\displaystyle{ v\in V }[/math]:
   1. An arc [math]\displaystyle{ (v,w)\in A }[/math] is an outgoing arc of [math]\displaystyle{ v }[/math], and an arc [math]\displaystyle{ (w,v)\in A }[/math] is an incoming arc of [math]\displaystyle{ v }[/math].
   2. The outdegree of [math]\displaystyle{ v }[/math] is the number of its outgoing arcs, the indegree of [math]\displaystyle{ v }[/math] is the number of its incoming arcs.

Representations of graphs

We focus on directed graphs [math]\displaystyle{ G=(V,A) }[/math] because an undirected graph is usually represented as a symmetric directed graph as introduced above. Let [math]\displaystyle{ n:=|V| }[/math] and [math]\displaystyle{ m:=|A| }[/math]. Without loss of generality, we assume [math]\displaystyle{ V=\{1,\ldots,n\} }[/math], and we write [math]\displaystyle{ A=\{a_1,\ldots,a_m\} }[/math]..

1. Adjacency matrix: an [math]\displaystyle{ (n\times n) }[/math]-matrix [math]\displaystyle{ M }[/math] wit 0/1 entries such that, for all [math]\displaystyle{ i,j\in V }[/math], [math]\displaystyle{ M[i,j]=1 }[/math] if, and only if, [math]\displaystyle{ (i,j)\in A }[/math].
2. Incidence matrix: an [math]\displaystyle{ (n\times m) }[/math]-matrix [math]\displaystyle{ M }[/math] such that, for [math]\displaystyle{ i\in\{1,\ldots,n\} }[/math] and [math]\displaystyle{ j\in\{1,\ldots,m\} }[/math], it is:
   1. [math]\displaystyle{ M[i,j]=+1 }[/math] if [math]\displaystyle{ i }[/math] is the head of [math]\displaystyle{ a_j }[/math].
   2. [math]\displaystyle{ M[i,j]=-1 }[/math] if [math]\displaystyle{ i }[/math] is the tail of [math]\displaystyle{ a_j }[/math].
   3. [math]\displaystyle{ M[i,j]=0 }[/math], otherwise.
3. Incidence lists: Each node has a list of its outgoing arcs (possibly, a list of its incoming arcs in addition). Each list is attached to its node, or all lists are organized in a separate data structure, for example, an array or a map.

Transpose of a graph

For a directed graph [math]\displaystyle{ G=(V,A) }[/math], the transpose of [math]\displaystyle{ G }[/math] results from [math]\displaystyle{ G }[/math] by turning all arcs.

Subgraphs

1. Let [math]\displaystyle{ G_1=(V_1,E_1) }[/math] and [math]\displaystyle{ G_2=(V_2,E_2) }[/math] be two simple undirected graphs. Then [math]\displaystyle{ G_1 }[/math] is a subgraph of [math]\displaystyle{ G_2 }[/math] if there is [math]\displaystyle{ V'\subseteq V_2 }[/math] and a bijection [math]\displaystyle{ \varphi:V_1\rightarrow V' }[/math] such that [math]\displaystyle{ \{v,w\}\in E_1 }[/math] implies [math]\displaystyle{ \{\varphi(v),\varphi(w)\}\in E_2\} }[/math]. If [math]\displaystyle{ \{\varphi(v),\varphi(w)\}\in E_2\} }[/math] also implies [math]\displaystyle{ \{v,w\}\in E_1 }[/math] for all [math]\displaystyle{ v,w\in V' }[/math], [math]\displaystyle{ G_1 }[/math] is called the (unique) induced subgraph of [math]\displaystyle{ G_2 }[/math].
2. Let [math]\displaystyle{ G_1=(V_1,A_1) }[/math] and [math]\displaystyle{ G_2=(V_2,A_2) }[/math] be two simple directed graphs. Then [math]\displaystyle{ G_1 }[/math] is a subgraph of [math]\displaystyle{ G_2 }[/math] if there is [math]\displaystyle{ V'\subseteq V_2 }[/math] and a bijection [math]\displaystyle{ \varphi:V_1\rightarrow V' }[/math] such that [math]\displaystyle{ (v,w)\in A_1 }[/math] implies [math]\displaystyle{ \{\varphi(v),\varphi(w)\}\in A_2\} }[/math]. If [math]\displaystyle{ \{\varphi(v),\varphi(w)\}\in A_2\} }[/math] also implies [math]\displaystyle{ \{v,w\}\in A_1 }[/math] for all [math]\displaystyle{ v,w\in V' }[/math], [math]\displaystyle{ G_1 }[/math] is called the (unique) induced subgraph of [math]\displaystyle{ G_2 }[/math] with respect to [math]\displaystyle{ V' }[/math] (induced by [math]\displaystyle{ V' }[/math]).
3. A spanning subgraph of an undirected or directed graph [math]\displaystyle{ G }[/math] is a subgraph that contains all nodes of [math]\displaystyle{ G }[/math]:

Paths

1. A path in an undirected graph is a finite sequence [math]\displaystyle{ (\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_k\}) }[/math] of edges such that, for [math]\displaystyle{ i\in\{1,\ldots,k-1\} }[/math], [math]\displaystyle{ e_i }[/math] and [math]\displaystyle{ e_{i+1} }[/math] are incident.
2. An (ordinary) path in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k)) }[/math].
3. A generalized path in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k)) }[/math] such that turning some of the arcs yields an ordinary path (possible, no arc to turn, that is, ordinary paths are generalized paths).
4. The internal nodes of a path of any kind are all nodes on this path except for the start and the end node (if the start or end node appears more than once on the path, it is also an internal node).
5. Two paths are edge-disjoint (resp., arc-disjoint) if they have no edge (arc) in common. They are called (internally) node-disjoint if they have no node in common that is internal on either path.

Remark:

1. Frequently, a path is viewed as an alternating sequence of the arcs/edges and the nodes on that path.
2. In simple graphs, a path is often identified with the sequence of nodes on this path.

Cycles

1. A cycle in an undirected graph is a path such that [math]\displaystyle{ v_1=v_k }[/math] (in the notation used in the section on paths).
2. An (ordinary) cycle in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_1)) }[/math].
3. A generalized cycle in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite sequence [math]\displaystyle{ ((v_1,w_1),(v_2,w_2),\ldots,(v_{k-1},w_{k-1}),(v_k,w_k)) }[/math] such that turning some of the arcs yields an ordinary cycle (possible, no arc to turn, that is, ordinary cycles are generalized cycles).
4. An undirected or directed graph is acyclic (a.k.a. cycle-free) if it contains no cycle. In the directed case, an acyclic graph is called a DAG (short for directed acyclic graph).

Connectedness

Types of connectedness:

1. An undirected graph is said to be connected if, for each pair of nodes, there is a path connecting this pair. It is [math]\displaystyle{ k }[/math]-connected if each pair of nodes is connected by at least [math]\displaystyle{ k }[/math] internally node-disjoint paths. In particular, connected means 1-connected. For [math]\displaystyle{ k=2 }[/math], we speak of biconnected.
2. A directed graph is said to be weakly connected if, for each pair of nodes, there is a generalized path connecting this pair. It is even strongly connected if, for each ordered pair of nodes, there is a path from the first node to the second node.

Connected components:

1. The [math]\displaystyle{ k }[/math]-connected components of an undirected graph [math]\displaystyle{ G=(V,E) }[/math] are the maximal node sets [math]\displaystyle{ V'\subseteq V }[/math] such that the induced subgraph is [math]\displaystyle{ k }[/math]-connected. For [math]\displaystyle{ k=1 }[/math] and [math]\displaystyle{ k=2 }[/math], we speak of the connected and biconnected components, respectively.
2. The weak and strong components of a directed graph are the maximal node sets [math]\displaystyle{ V'\subseteq V }[/math] such that the induced subgraph is weakly and strongly connected, respectively.

Remark: Maximality of the components implies that the components form a partition of the node set in each case.