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.

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.

Cycles

1. A cycle in an undirected