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.

Paths

1. A path in an undirected graph is a sequence <math>

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 fro the first node to the second one.