Graph Concepts

Internal

• Graphs

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(n²). 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.

Parallel Arcs

Two parallel arcs (or parallel edges) are two arcs that have the same vertices.

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. Directed edges are called arcs.

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 (2, 2), (2, 4) and (2, 5) leave vertex 2, and (2, 2) and (1, 2) enter vertex 2.

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:

1. the values of f(v) are the set {1, 2, ..., n}
2. (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:

Topological Sort of a Directed Acyclic Graph

Graph Density

Sparse Graphs

A sparse graph is a graph for which │E│ is much smaller than │V│². 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│². Otherwise said, for a dense graph m is closer to O(n²).