Basic graph definitions

Basic definitions

1. Sets and sequences

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] or [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. A node with degree zero is isolated.
5. Consider a directed graph [math]\displaystyle{ G=(V,A) }[/math]:
   1. For an arc [math]\displaystyle{ a=(v,w)\in A }[/math], [math]\displaystyle{ v }[/math] is the tail of [math]\displaystyle{ a }[/math], and [math]\displaystyle{ w }[/math] is the head of [math]\displaystyle{ a }[/math].
   2. An arc [math]\displaystyle{ (v,w)\in A }[/math] is an outgoing arc of [math]\displaystyle{ v }[/math], and an incoming arc of [math]\displaystyle{ w }[/math].
   3. The outdegree of a node [math]\displaystyle{ v\in V }[/math] is the number of its outgoing arcs, the indegree of [math]\displaystyle{ v }[/math] is the number of its incoming arcs.

Statement: If there are no isolated nodes, the number of edges/arcs dominates the number of nodes asymptotically.

Proof: In this case, the number of edges/arcs is at least half the number of nodes.

Remark: In many algorithmic problems on graphs, isolated nodes may be removed before the algorithm commences.

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] with 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, alternatively, all lists are organized in a separate data structure, for example, an array or a map such that the list is easily accessible given the node. In each arc, the head and, possibly, the tail are stored as attributes.

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.

Remark: In many applications, the arcs have attributes such as lengths, capacities, cost factors, etc. These attributes are maintained when the arcs are turned. In most cases, this means they are not changed at all. There are exceptions, for example, cost factors are to be negated in some contexts.

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_1 }[/math], [math]\displaystyle{ G_1 }[/math] is called the (unique) induced subgraph of [math]\displaystyle{ G_2 }[/math] (we say, induced by [math]\displaystyle{ V' }[/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] (we say, 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. An (ordinary) path in an undirected graph is a finite ordered 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.
2. An (ordinary) path in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite ordered sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_k)) }[/math] of arcs.
3. A generalized path (a.k.a. weak 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 (possibly, no arc to turn, that is, ordinary paths are generalized paths).
4. A path is simple if it does not meet any node more than most once.
5. A node [math]\displaystyle{ t\in V }[/math] is reachable from [math]\displaystyle{ s\in V }[/math] if there is a path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] in the graph. Depending on the context, the path must be an undirected, an ordinary directed, or a generalized path. Each node is reachable from itself via the trivial path that contains this node only and no edges/arcs.
6. 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).
7. 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. An (ordinary) cycle in an undirected graph is a finite ordered sequence [math]\displaystyle{ (\{v_1,v_2\},\{v_2,v_3\}\dots,\{v_{k-2},v_{k-1}\},\{v_{k-1},v_1\}) }[/math] of edges; in other words, a path such that start node and end node are identical.
2. An (ordinary) cycle in a directed graph [math]\displaystyle{ G=(V,A) }[/math] is a finite ordered sequence [math]\displaystyle{ ((v_1,v_2),(v_2,v_3),\ldots,(v_{k-2},v_{k-1}),(v_{k-1},v_1)) }[/math] of arcs; in other words, a path such that start node and end node are identical.
3. A generalized cycle (a.k.a. weak 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 (possibly, no arc to turn, that is, ordinary cycles are generalized cycles).
4. A cycle is simple if no proper part is a cycle of its own.
5. An undirected or directed graph is acyclic (a.k.a. cycle-free) if it contains no ordinary cycle. In the directed case, an acyclic graph is usually called a DAG (short for directed acyclic graph).
6. For [math]\displaystyle{ s,t\in V }[/math], an [math]\displaystyle{ (s,t) }[/math]-graph [math]\displaystyle{ G=(V,A) }[/math] is a DAG such that [math]\displaystyle{ s }[/math] is the only node with indegree zero, and [math]\displaystyle{ t }[/math] is the only node with outdegree zero. It is easy to see that a DAG is an [math]\displaystyle{ (s,t) }[/math]-graph if, and only if, [math]\displaystyle{ G }[/math] is the union of (not necessarily internally node-disjoint or arc-disjoint) [math]\displaystyle{ (s,t) }[/math]-paths.

Forests, trees, branchings, arborescences

1. A forest is a cycle-free undirected graph. A tree is a connected forest.
2. A branching is a cycle-free directed graph such that the indegree of each node is zero or one. An arborescence is a branching such that exactly one node has indegree zero (note that, for branchings, this condition is equivalent to weak connectedness). Arborescences are also known as rooted trees, and the unique node with indegree zero is the root.
3. A forest/tree/branching/arborescence in a graph [math]\displaystyle{ G }[/math] is a subgraph of [math]\displaystyle{ G }[/math] that is a forest/tree/branching/arborescence. A forest/tree/branching/arborescence is spanning if it contains all nodes of [math]\displaystyle{ G }[/math] (cf. here).

Statement: For a forest, let [math]\displaystyle{ n }[/math] denote the number of nodes, [math]\displaystyle{ m }[/math] the number of edges, and [math]\displaystyle{ k }[/math] the number of trees in this forest. Then it is [math]\displaystyle{ m=n-k }[/math]. In particular, for a tree, it is [math]\displaystyle{ m=n-1 }[/math].

Proof: Obviously, it suffices to prove [math]\displaystyle{ m=n-1 }[/math] for trees. This is proved by an induction on the number [math]\displaystyle{ n\geq 1 }[/math] of nodes. For [math]\displaystyle{ n=1 }[/math], it is [math]\displaystyle{ m=0 }[/math], so consider the case [math]\displaystyle{ n\gt 1 }[/math]. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path [math]\displaystyle{ p }[/math] in terms of the number of edges. Then [math]\displaystyle{ p }[/math] is not extensible, so its two end nodes have degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.

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 an ordinary path from the first node to the second node.

Links:

1. An articulation node in a connected undirected graph is a node such that the graph becomes disconnected when this node and its incident arcs are removed.
2. A bridge in a connected undirected graph is an edge such that the graph becomes disconnected when this edge is removed.

Connected components:

1. The [math]\displaystyle{ k }[/math]-connected components of an undirected graph [math]\displaystyle{ G=(V,E) }[/math] are the inclusion-maximal node sets [math]\displaystyle{ V'\subseteq V }[/math] such that the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ V' }[/math] 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 of [math]\displaystyle{ G }[/math], respectively.
2. The weakly and strongly connected components (weak and strong components, for short) of a directed graph [math]\displaystyle{ G=(V,A) }[/math] are the inclusion-maximal node sets [math]\displaystyle{ V'\subseteq V }[/math] such that the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ V' }[/math] is weakly and strongly connected, respectively. The term strongly connected component is usually abbreviated by SCC.

Remark: Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.

Bipartite and k-partite graphs

Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph.

1. [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-partite if there is a [math]\displaystyle{ k }[/math]-partition [math]\displaystyle{ \{V_1,\ldots,V_k\} }[/math] of [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ \{v,w\}\not\in E }[/math] for any pair [math]\displaystyle{ v,w\in V_i }[/math] for any [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math].
2. For [math]\displaystyle{ k=2 }[/math], we say that [math]\displaystyle{ G }[/math] is bipartite.

Statement: An undirected connected graph is bipartite if, and only if, it contains no cycle of odd length.

Proof: First suppose that [math]\displaystyle{ G=(V,E) }[/math] is bipartite with bipartition [math]\displaystyle{ V=V_1\dot\cup V_2 }[/math]. Let [math]\displaystyle{ v_1-\cdots-v_k-v_1 }[/math] be the nodes on some cycle in this order. Without loss of generality, let [math]\displaystyle{ v_1\in V_1 }[/math]. A straightforward induction on [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math] shows that [math]\displaystyle{ v_i\in V_1 }[/math] for [math]\displaystyle{ i }[/math] odd and [math]\displaystyle{ v_i\in V_2 }[/math] for [math]\displaystyle{ i }[/math] even. The assumption [math]\displaystyle{ v_1\in V_1 }[/math] implies [math]\displaystyle{ v_k\in V_2 }[/math], so [math]\displaystyle{ k }[/math] must be even.

Now suppose there is no cycle of odd length in [math]\displaystyle{ G }[/math]. Start a BFS from some start node [math]\displaystyle{ s\in V }[/math]. Create a bipartition of [math]\displaystyle{ V }[/math] as follows: Each node of even distance from [math]\displaystyle{ s }[/math] is in [math]\displaystyle{ V_1 }[/math], and all other nodes are in [math]\displaystyle{ V_2 }[/math]. Suppose for a contradiction that there is an edge [math]\displaystyle{ \{v,w\}\in E }[/math] such that either [math]\displaystyle{ v,w\in V_1 }[/math] or [math]\displaystyle{ v,w\in V_2 }[/math]. Let [math]\displaystyle{ u }[/math] be the last node such that the paths from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] in the arborescence are identical up to [math]\displaystyle{ u }[/math] (possibly, [math]\displaystyle{ u=s }[/math]). Let [math]\displaystyle{ p_1 }[/math] and [math]\displaystyle{ p_2 }[/math] denote the paths from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] in the arborescence. Then the concatenation [math]\displaystyle{ p_1+p_2+\{v,w\} }[/math] is a cycle of odd length.

Complete graphs

1. For a positive integral number [math]\displaystyle{ n }[/math], the complete graph [math]\displaystyle{ K_n=(V,E) }[/math] is the unique undirected graph such that [math]\displaystyle{ |V|=n }[/math] and all (unordered) pairs of nodes are in [math]\displaystyle{ E }[/math].
2. For positive integral numbers [math]\displaystyle{ m }[/math] and [math]\displaystyle{ n }[/math], the complete bipartite graph [math]\displaystyle{ K_{m,n}=(V_1\dot\cup V_2,E) }[/math] is the unique undirected graph such that [math]\displaystyle{ |V_1|=m }[/math] and [math]\displaystyle{ |V_2|=n }[/math], and each (unordered) pair [math]\displaystyle{ \{v,w\} }[/math] with [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math] is in [math]\displaystyle{ E }[/math].