Graph Concepts
Internal
Graph Definition
A graph is a pair-wise relationship among a set of objects. Mathematically, a graph G is a pair (V, E), where V is a finite set of vertices, called the vertex set of G, and E is a binary relation on G, called the edge set of G, which contains the graph's edges.
n and m Convention
In graph problems, the usual convention is to denote the number of vertices with n and the number of edges with m. In most, but not all, applications, m is Ω(n) and O(n2). Also see sparse graphs and dense graphs.
Vertices and Edges
Vertex (Node)
An elements of the vertex set V is called vertex (plural vertices). A vertex has zero or more edges associated with it. An alternate term for vertex, used sometimes in the graph theory literature, is node. We prefer to use the term "node" when we refer to the vertices of rooted trees. We use "vertex" as a more generic term that refers to graphs in general. Another alternate name is entity.
Edge (Arc)
The element of the edge set E are called edges (also known as relationships or arcs). By convention, we use (u, v) notation for an edge, where u and v represent vertices in V. The order in which vertices are specified for an edge may be relevant. If the order in which the vertices are specified matters, then the graph is a directed graph. If the order in which the vertices are specified does not matter, then the graph is an undirected graph.
For undirected graphs, edges are said to be incident on vertices, while for directed graphs, edges can be incident to and from vertices.
Parallel Arcs
Two parallel arcs (or parallel edges) are two arcs that have the same vertices.
Self-Loops
A self-loop is an edge incident from and incident to the same vertex. Self loops are only allowed in directed graphs.
Vertex Adjacency
If (u, v) is an edge in a graph G = (V, E), we say that the vertex v is adjacent to vertex u. In other words, if two vertices have an edge connecting them, they are adjacent. For undirected graphs, the adjacency relation is symmetric: if vertex u is adjacent to vertex v, then automatically vertex v is adjacent to vertex u. This is not the case for directed graphs: u → v ≠ v → u.
Vertex Degree
The vertex degree is the count of edges incident on, from and to the vertex, depending on the type of the graph.
For undirected graphs, the vertex degree is the number of edges incident on the vertex, which is the same with the number of adjacent vertices. In the example below, the vertex v has degree 2.
For an undirected graphs, the following relationship holds true:
∑ degree(v) = 2m v
For directed graphs, we define the in-degree as the number of edges entering the vertex and the out-degree as the number of edges exiting the vertex. The degree of the vertex is the sum of in-degree and out-degree. In the example above, vertex v has an in-degree 2, out-degree 3 and degree 5.
Graph Directionality
Undirected Graph
An undirected graph is a (V, E) pair where the edge set E contains undirected edges: the order in which the vertices are specified when the edge is defined does not matter and (u, v) is equivalent with (v, u) - they are considered to be the same edge. Another way to define an unordered graph is that its edges are sets {u, v} where u, v ∈ V and u ≠ v.
⚠️ Self-loops are not allowed in an undirected graph. Every edge consists of two distinct vertices.
If (u, v) is an edge in an undirected graph G = (V, E), we say that (u, v) is incident on both vertices u and v. In the example above, edges incidents on vertex v are (u, v) and (v, s).
An undirected graph in which each pair of vertices is adjacent is called a complete graph.
A forest is an acyclic, undirected graph. Note that the graph may be disconnected.
A tree is a connected, acyclic, undirected graph. A tree defined as such is sometimes referred to as a free tree. More details about trees are available in the Tree Concepts section.
Directed Graph
A directed graph is a (V, E) pair where the edge set E contains directed edges: the order in which the vertices are specified when the edge is defined matters. For a directed graph, (u, v) and (v, u) are distinct edges. That is why we sometimes write the edge as u → v and v → u.
A characteristic of a directed graph is that self-loops, edges from a vertex to itself, are allowed. A self-loop is a cycle of length 1.
A directed graph with no self-loops is simple.
If (u, v) is an edge in a directed graph G = (V, E), we say that (u, v) (u → v) is:
- incident from, or leaves vertex u. Another formulation is that u is the tail vertex.
- incident to, or enters, vertex v. v is the head vertex.
In the example above, edges (v, v), (v, p) and (v, s) leave vertex v, and (v, v) and (u, v) enter vertex v.
TODO: https://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/digraph.4up.pdf
Topological Order of a Directed Graph
A topological order of a directed graph G is a function (labeling) f of G's nodes such that:
- the values of f(v) are the set {1, 2, ..., n}
- (u, v) ∈ G ⇒ f(u) < f(v)
All edges go "forward" when we place the nodes in a line.
A directed graph has a topological ordering only if it is acyclic, or a directed acyclic graph (DAG). If the directed graph has a directed cycle, there cannot be a topological ordering of that graph. On the other hand, if a directed graph has no directed cycles, this condition is strong enough to guarantee that a topological order can be computed - the graph can be topologically sorted.
Also see:
Graph Density
Sparse Graphs
A sparse graph is a graph for which │E│ is much smaller than │V│2. Otherwise said, for a sparse graph m is O(n) or close to it.
Dense Graphs
A dense graph is a graph for which │E│ is close to │V│2. Otherwise said, for a dense graph m is closer to O(n2).
Paths
A path of length k from a vertex u to a vertex u' in a graph G = (V, E) is a sequence (v0, v1, ..., vk) of vertices such that u = v0, u' = vk and the edge (vi-1, vi) ∈ E for i = 1, 2, ... k. Some sources refer to a path as a "walk".
The length of the path is the number of edges in the path.
We say that the path contains the vertices v0, ..., vk and the edges (v0, v1), (v1, v2), ..., (vk-1, vk).
There is always a zero-length path from u to u.
If there is a path p from u to u', we say that u' is reachable from u via path p.
A path is simple if all vertices in it are distinct. In the directed graph example above, the path (u, v, p, s) is a simple path of length 3. The path (v, p, s, p) is not simple.
A subpath of a path p = (v0, v1, ..., vk) is a contiguous subsequence of its vertices: for any 0 ≤ i ≤ j ≤ k, the subsequence of vertices (vi, vi+1, ..., vj) is a subpath.
Cycles
Undirected Graphs Cycles
For undirected graphs, a path (v0, v1, ..., vk) forms a cycle if k ≥ 3 and v0 = vk. The circle is simple if v1, v2, ..., vk are distinct.
Directed Graphs Cycles
For directed graphs, a path (v0, v1, ... vk) forms a cycle if v0 = vk and the path contains at least one edge. The cycle is simple if, in addition, v1, v2, ... vk are distinct.
A self-loop is a cycle of length 1.
Two paths (v0, v1, ...., vk-1, v0) and (v'0, v'1, ...., v'k-1, v'0) form the same cycle if there exists an integer j such that v'i = v(i + j) mod k for i = 0, 1, ..., k - 1.
Acyclic Graphs
An acyclic graph is a graph that has no cycles.
Directed Acyclic Graph (DAG)
A directed acyclic graph is a directed graph that has no directed cycles - paths that start from a node, follow the directed edges and return to the same node. It is sometimes abbreviated to DAG. One of the practical applications of DAGs is to model dependencies between entities: a directed edge between vertices u and v means that u is a pre-requisite for v, u needs to happen first, or v depends on u. Directed acyclic graphs have a topological ordering. The depth-first search algorithm can be used to compute the topological sort of a directed acyclic graph:
Sink Vertex
Every directed acyclic graph has one or more sink vertices, which are vertices without any outgoing arcs. A directed graph without a sink vertex must have a cycle, hence is not a directed acyclic graph. The sink vertex concept is useful in the straightforward implementation of the topological sorting algorithm of DAGs.
Connectivity and Graph Components
Undirected Graph Connectivity
An undirected graph is connected if every vertex is reachable from all other vertices.
Connected Component
A connected component of a graph is the equivalence class of the relation between vertices u ~ v ⇔ ∃ u-v path in G.
The connected components of a graph are the equivalence classes of vertices under the "is reachable from" relation. The undirected graph example above has three connected components: {u, v, s}, {w, q} and {p}. The edges of a connected component are those that are incident only on the vertices of the component; in other words, the edge (u, v) is an edge of a connected component only if both u and v are vertices of the component.
An entire undirected graph is connected if it has exactly one connected component.
The connected components of an undirected graph can be computed with a breadth-first search-based algorithm:
Directed Graph Connectivity
A directed graph is strongly connected if every two vertices are reachable from each other.
Strongly Connected Component
The strongly connected components (SCC) of a directed graph are the equivalence classes of vertices under are mutually reachable relation.
The formal definition of strongly connected component (SCC) of a directed graph G is the equivalence classes of the relation:
u ~ v ⇔ ∃ a path u → v and
∃ a path v → u in G
An entire directed graph is strongly connected if it has only one strongly connected component.
The strongly connected components of an directed graph can be computed with the algorithm, which is based on depth-first search:
Finding the strongly connected components of a directed graph is an application of a depth-first search:
Isomorphic Graphs
Two graphs G = (V, E) and G' = (V', E') are isomorphic if there exists a bijection f : V → V' such that (u, v) ∈ E if and only if (f(u), f(v)) ∈ E'. This also can be expressed as follows: we can relabel the vertices of G to be vertices of G', maintaining the corresponding edges in G and G'.
Subgraphs
We say that a graph G' = (V', E') is a subgraph of G = (V, E) if V' ⊆ V and E' ⊆ E.
Given a set V' ⊆ V, the subgraph of G induced by V' is the graph G' = (V', E') where E' = {(u, v) ∈ E: u, v ∈ V'}.
Contraction
The contraction of an undirected graph G = (V, E) by an edge e = (u, v) is a graph G' = (V', E') where V' = V - {u, v} ⋃ {x} and x is a new vertex. The set of edges E' is formed from E by deleting the edge (u, v) and, for each vertex w incident on u or v, deleting whichever of (u, w) and (v, w) is in E and adding the new edge (x, w). In effect, u and v are "contracted" into a single vertex.