Graphs
Table of Contents
1. Introduction
We denote a graph as \( G(V, E) \), where \( V = \{ v_1, v_2 ... v_n \} \) is the vertex set of the graph and \( E = \{ (v_a, v_b) ... (v_c, v_d) \} \) as the edge set of the graph.
If \( G \) is a directed graph then the elements of \( E \) will be ordered (ie \( (v_1, v_2) \) is distinct from \( (v_2, v_1) \)), otherwise \( G \) is undirected.
We also say \( G \) is simple if there is at most on edge connecting any pair of vertices, and no edges connecting a vertex to itself.
2. Vertex Sequences
2.1. Definition
A walk in a graph \( G(V, E) \) is a finite sequence of vertices \( (v_1 ... v_k) \) such that each consecutive pair forms an edge of \( G \).
2.2. Definition
A trail (or tour) is a walk in which all the edges \( e_i = (v_i, v_{i + 1}) \) are distinct. We can remember this by associating them with Eulerian trails (which much visit every edge exactly once).
2.3. Definition
A path is a trail in which a vertex occurs occurs only once in the edge sequence.
2.4. Definition
A cycle is a trail in which all the vertices are distinct, except for the first and last which are the same.
3. Subgraphs
3.1. Definition
A clique is a set of vertices \( S \subseteq V \) such that the subgraph induced by \( S \) forms a complete graph.
3.2. Definition
An independent set, I, of \( G(V, E) \) is a set \( I \subseteq V \) such that no pair of vertices in \( I \) is joined by an edge in \( E \).
3.3. Definition
Let \( G(V, E) \) be a graph, then the graph complement of \( G \) is a graph \( H(V, E') \) such that \( e \in E' \iff e \not \in E \).
4. Adjacency Matrices
Given a directed or undirected graph \( G(V, E) \) on \( n \) vertices, we define the adjacency matrix, \( A \), of \( G \) as an \( n * n \) matrix with entries given by:
\[ A_{i, j} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases} \]
This is always symmetric if \( G \) is undirected, and zeroes always fill the main diagonal if \( G \) is simple.
4.1. Applications
Note \( (A^k)_{i, j} \) gives the number of paths of length \( k \) starting at \( v_i \) and ending at \( v_j \). Hence using matrix associativiy we can compute this value in \( O(log(k)) \) or \( O(1) \) time.
We can extends this to find the number of paths of length \( 1 \le x \le k \) starting at \( v_i \) and ending at \( v_j \), by noting this is equal to:
\[ (A + A^2 + ... + A^k)_{i, j} = \left( A(A^k - I_n)(A - I_n)^{-1} \right)_{i, j} \]
Which can be computed in the same time complexity.