Graph theory

A graph $G$ consists of a pair of finite sets, $V(G)$ of vertices and $E(G)$ of edges. Each edge has a set of either one or two vertices called its endpoints. Graph theory is the study of the mathematics of graphs.

There are two main ways to represent a graph: as a collection of adjacency lists or as an adjacency matrix. List representations are ideal if $|E|$ is much less than $|V{|}^2$, i.e., if the graph is sparse. Matrix representations are ideal for dense graphs, i.e., if $|E|$ is close to $|V{|}^2$.

Quick links:

• LeetCode problem list
  • DFS
  • BFS
  • Topological sort

Basic terminology

An edge with one endpoint is called a loop. Two or more distinct edges with the same endpoints are parallel. An edge connects its endpoints, and two vertices connected by an edge are adjacent. If a vertex is an endpoint of a loop, then it is adjacent to itself. An edge is incident on each of its endpoints. Two edges incident on the same endpoint are adjacent. A vertex with no incident edges is isolated.

A directed graph (or digraph) is where the edges have a direction, i.e., for $e=(v_1,v_2)\in E$, $v_1$ is a source and $v_2$ is a target for $e$. An acyclic graph has no loops. Acyclic directed graphs (or dags) are an important type of graph.

A simple graph doesn’t have any loops or parallel edges. A complete graph on $n$ vertices (where $n\in {\mathbb{Z}}^{+}$) is a simple graph with $n$ vertices and exactly one edge connecting each pair of distinct vertices. A graph $H$ is a sub-graph of $G$ if every vertex in $H$ is also a vertex in $G$, every edge in $H$ is also an edge in $G$, and every edge in $H$ has the same endpoints as it has in $G$.

The degree of a vertex $v$, $\mathrm{deg}(v)$, is the number of edges that are incident on $v$ (i.e., how many neighbours it has). An edge that is a loop is counted twice. The total degree of $G$ is the sum of the degrees of all the vertices of $G$.

A path in the graph is a sequence $a_j,j\in [1,\cdots ,k]$ where $a_1,a_k\in V$ (i.e., the start and end of the sequence are vertices). Additionally, for every $j<k$, if $a_j\in V$, then $a_{j+1}\in E$. If $a$ is a path, the length is the number of edges in the path.

A weighted graph is one where each edge has an associated weight given by a weight function $w:E\to \mathbb{R}$.

A subgraph is defined as a graph $G^{\prime }$ with vertices/edges $V^{\prime },E^{\prime }$ if and only if $V^{\prime }\subset V\wedge E^{\prime }\subset E$, and if $e=(v,u)\in E^{\prime }$, then $v\in V^{\prime },u\in V^{\prime }$. In other words, a graph $G^{\prime }$ is a subgraph of $G$ if all of its vertices are a subset of $G$‘s vertices, and all of its edges are a subset of $G$‘s edges. There’s also a restriction that any edge $e\in E^{\prime }$ must have its vertices in $V^{\prime }$ as well.

More terminology

Graphs with $n$ vertices have:

• At least:
  • Connected graphs: $n-1$ edges.
  • Unconnected graphs: 0 edges.
• At most:
  • Simple graphs: $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$.
  • Not simple: no upper bound
• In an undirected graph, the number of edges and degrees of the vertices is: ${\sum }_{v\in V}\text{deg}(v)=2m$, where $m$ is the number of edges.

Traversal can be done in a few specific ways:

• A walk is a sequence of vertices between which there are edges, but where vertices and edges can be repeated.
• A trail is a walk with no repeated edges.
• A path is a trail with no repeated vertices, except at the start and end vertex.
• Circuits have trails that begin and end at the same vertex.
• Cycles have paths that begin and end at the same vertex. Graphs with cycles are cyclic. Trees are special acyclic, connected graphs.

Advanced terminology

For a directed graph $(V,E)$, a diagram on the graph is a family $(S_v{)}_{v\in V}$ of sets associated with each vertex and a family $(f_e{)}_{e\in E}$ of maps associated with each edge such that if $e\in (v_1,v_2)$, then $f_e$ has domain $S_{v_1}$ and codomain $S_{v_2}$.

If $P$ is a non-zero length path in a diagram on $(V,E)$, the composition along $P$ is the map $f_{e_k}\circ \cdots \circ f_{e_1}$. A diagram is commutative if for every two vertices $v_1,v_2\in V$ and any two paths $P_1,P_2$ with source $v_1$ and target $v_2$, the composition along $P_1$ is equal to the composition along $P_2$.

In other words, if there are two different paths between two vertices, the diagram is commutative if the composition of the maps along each path is equal.

homomorphisms, isomorphisms, automorphisms

Graph problems

The benefit of common graph traversal algorithms is that we can check the properties of graphs. For instance, some simple applications of these algorithms involve:

• Connectivity checks (i.e., are certain nodes connected to other nodes?)
• Finding graph cycles
• Checking for bipartiteness

In general, we should follow the same competitive programming problem-solving workflow. After reading and understanding the problem, we should consider what the best way to model the problem is. In particular, if the graph is given to us in a non-standard representation, we should convert to an adjacency list or matrix.

Sub-pages

• Graph algorithms
  • Traversal
    • Depth-first search (DFS)
    • Breadth-first search (BFS)
    • Topological sort
  • Shortest-path
    • Bellman-Ford algorithm
    • Dijkstra’s algorithm
    • Floyd-Warshall algorithm
    • A-star algorithm
  • Minimum spanning tree
    • Kruskal’s algorithm
    • Prim’s algorithm
  • Search
    • Union find
• Graph applications
  • Graph neural network
  • Graph database