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.

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).

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

1. An undirected graph is said to be connected if, for each pair of nodes, there is a path connecting this pair.
2. A directed graph is said to be weakly connected if, for each pair of nodes, there is a generalized path connecting this pair.
3. A directed graph is said to be strongly connected if, for each ordered pair of nodes, there is a path from the first node to the second one.

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].
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]: