6. Graph Theory

Definitions

Graph: $G(V,E)$ , where $V$ is a set of vertices, $E$ is a set of edges, each relating two vertices together. $$ n=|V| \ m=|E| \ m \le n^2 $$

Sparse graph: $m \in O(n)$
Dense graph: $m \in \Theta(n^2)$
Directed graph: edges are ordered pairs $E \subseteq V \times V$ , so one way.
Undirected graph: edges are a set of vertices, $E \in \{\{u,v\}, u,v \in V\}$

Weighted graphs: edges have a weight $\omega$ .

Path: a sequence of vertices where:

Each vertex is connected to each other by a edge
Each edge is not used more than once

Length of path: number of edges.

Cycle: path where the source and destination vertex is the same:

Cyclic if graph contains at least one cycle
- Acyclic if not
  - If it is also directed, it is called a directed acyclic graph
Loop: cycle of length one

Empty graph: $(\{\}, \{\})$ .

Subgraphs

$G'=(V',E')$ where $V' \subseteq V, E' \subseteq E$

Component: a non-empty subgraph where every pair of vertices connected by a path. If there is a path between two vertices, they are in the same component.

Tree: graph with a root vertex such that there is only one path between the vertex and root.

Directed tree: tree where all edges point either towards or away from the root.

Forest: graph where every component is a tree

Textual Representation of Graphs

Header:

D or U for directed/undirected
n: number of vertices (which are numbered from 0)
W: appears if it is a weighted graph

All other lines after the header define a edge: V1 V2 or V1 V2 Weight

Data Structures

Adjacency Matrix:

$n \times n$ binary matrix $A$ , where $A[i,j] = 1$ if $i$ and $j$ are connected to each other via a edge and 0 otherwise
If undirected, the matrix is symmetric along the main diagonal
If the graph is weighted, the value is the weight, or null if no edge

Adjacency List:

A list of length $n$ , each element being a list for every vertex
Each sub-list contains the vertices it is connected to ○ If directed, $j$ is in the list for $i$ if there is a edge $(i,j)$ ○ If the graph is weighted, each item in the list is of the form $(j,w)$

Adjacency matrices are faster ( $\Theta(1)$ vs $\Theta(n)$ ) for operations such as checking for the existence of an edge, adding, and deleting edges, but uses $\Theta(n^2)$ space compared with $\Theta(n)$ for adjacency lists.

Forests:

Each vertex has zero or one parents
Store as an array: if vertex $v$ has parent $u$ , $parent[v]=u$

Graph Traversal

Each vertex can be in one of three states:

Undiscovered
Discovered
Processed

Predecessor Tree:

Root: starting vertex
For $u$ in the list of vertices:
- If $(u,v)$ or $(u, v)$ , where $v$ is undiscovered:
  - Add $v$ to the tree: $v$ is the child of $u$ (even if the graph is undirected)
    - Set $parent(u) = v$ . Note that this is different from the forest map as a child can have multiple parents, but will only ever specify one parent: whatever was first

BFS

Two procedures: BFS-Tree initializes the data structure and calls BFS-Loop:

def BFSTree(adj, index):
  # Where:
  # - adj is the adjacency matrix
  # - index is the index of the root
  n = len(vertices)
  state = [UNDISCOVERED * n]
  state[index] = DISCOVERED

  parent = [NULL * n]
  Q = Queue()
  Q.add(index)
  return BFSLoop(adj, Q, state, parent)

def BFSLoop(adj, Q, state, parent):
   while Q is not empty:
    u = Q.remove()
    for v in adj[u]:
      # For each vertex u is connected to
      if state[v] == UNDISCOVERED:
        state[v] = DISCOVERED
        parent[v] = u
        Q.add(v)
    state[u] = PROCESSED
  return parent

Analysis

Size of $G$ : $|V|=n$ , $|E|=m$ , where $m \le n^2$ .

Time complexity of BFSTree: $\Theta(n)$
Time complexity of BFSLoop: proportional to number of times the loop is run, so maximum of number of edges in the graph: $O(m)$

So complexity is $O(n+m)=O(\max(n,m))$

DFS

def DFSLoop(adj, index, state, parent):
  for v in adj[index]:

    # For each vertex the given index is connected to
    if state[v] == UNDISCOVERED:
      state[v] = DISCOVERED
      parent[v] = index
      DFSLoop(adj, v, state, parent)
    state[index] = PROCESSED
  return parent

Properties of DFS and BFS

Works with directed and undirected, although weights are ignored
Only creates a single tree
DFS can be done by replacing BFS queue with stack, and replacing enqueue and dequeue with push and pop
BFS: vertices discovered in order of increasing distance from start
DFS: vertex only marked as processed once all vertices reachable from it are discovered

Shortest Path

Use BFS to produce parent/predecessor tree, working backwards from the end until you get to the start.

def treePath(parentTree, start, end):
    if start == end:
        return [start]
    path = treePath(parentTree, start, parentTree[end])
    path.append(end)
    return path

Connected Components

When BFS or DFS is run, all vertices reachable from the start node are processed: that is, it finds a subgraph.

Thus, to find all components, run BFS or DFS on each vertex that has not yet been discovered. To make sorting the vertices into components easier, there can be an array that stores the component number; on what run of the DFS/BFS the vertex was first discovered.

Strong Connectivity

A directed graph is strongly connected If there is a path between every ordered pair of vertices.

This can be determined inefficiently by running BFS and check if all vertices are processed for all possible starting vertices.

Transpose operation, $G^T$ : for all edges, reverse the order:

Adjacency matrix: mirror along the main diagonal. $\Theta(n^2)$
Adjacency list: $\Theta(m+n)$

Hub: vertex $h$ is a hub if $h$ is reachable from every vertex AND $h$ can visit every vertex.

If there is such a vertex, then the graph must be strongly connected as any vertex can go through $h$ to get to any other vertex. Thus, if there is a hub, every vertex is a hub. To determine this:

Run a traversal starting with $h$
Return false if any vertex is undiscovered
Construct the transpose of the graph
Run a traversal on the transpose starting at $h$
Return false if any vertex is undiscovered

Thus, time complexity is the same as graph traversal: $O(n+m)$

Topological Ordering (DAGs only)

Ordering of vertices such that if $(u,v)$ exists, $u$ is ordered before $v$ .

All DAGs have at least one such ordering.

Programs such as make will use it to find a valid order to compile rules; package installers will use it to find the correct installer to install dependencies.

Initialize empty stack
For each vertex:
- If undiscovered, start modified DFS: when vertex is processed, push it to the stack
  - The vertex at the end will be pushed to the stack first
  - This ordering will continue until it gets to the start vertex
  - When the DFS is run again with another start vertex, if it is ‘before’ the previous start vertex, vertices between the two will get added to the stack
Return the stack from top to bottom

Cycle Detection

Directed graphs: run DFS: if a vertex that has already been discovered is reached, there is a cycle. Run this with each possible starting vertex, or until a loop has been discovered.

Run DFS: if, while on vertex $u$ , if $u$ goes to $v$ and $v$ has already been discovered, there is a loop. If the graph is undirected, ignore the vertex $(u,parent[u])$ .

If the graph has multiple components, the DFS must be run multiple times, using a similar algorithm to when finding connected components.

Weighted Algorithms

Minimum Spanning Tree

Tree that includes all vertices of the graph and has the lowest total weight among all spanning trees. The graph must be undirected.

Prim’s Algorithm

Create a list: the parent of each vertex
Create a list: if a vertex is in the tree
Create an list containing the closest distance of a vertex to the tree, each with a starting value of infinity
While there are vertices remaining:
- Find the vertex v that is closest to the tree
  - For the first loop, pick vertex 0 (or anything, really)
- Add v to the list of vertices in the tree
- For all vertices still not in the tree:
  - If the distance between the vertex and v is smaller than the distance stored in the list
    - Update the distance, and set the parent of the vertex to v
Return the parent and distance

The algorithm is $O(n^2)$ , but if a heap-based priority queue used for the distance array, the time complexity of finding the next vertex is $O(\log{n})$ . Hence, the time complexity of the overall algorithm to $O(m+n\log{n}).$

def prim(adj):
# Prim's algorithm: minimum spanning tree
  in_tree  = [False]        * len(adj)
  distance = [float('inf')] * len(adj) # Stores distance from tree
  parent   = [None]         * len(adj)
  distance[0] = 0

  while False in in_tree:
    u = next_vertex(in_tree, distance)
    # Pick closest vertex not in tree. If distance is min heap with edit 
    # support, then function is log(n) and algorithm is nlog(n)
    in_tree[u] = True
    for (vertex, weight) in adj[u]:
      if not in_tree[vertex] and weight < distance[vertex]:
        distance[vertex] = weight
        parent  [vertex] = u
  
  return (parent, distance)

Shortest Path Trees

The shortest path tree rooted at vertex $s$ is the spanning tree such that distance from root to any other vertex is the smallest possible.

Dijkstra’s Algorithm

NB: this will not always produce correct results on graphs with negative weights.

def dijkstra(adj, s):
  # adj = adjacency list
  # s = index for start vertex
  in_tree = [False]         * len(adj)
  distance = [float('inf')] * len(adj)
  parent = [False]          * len(adj)
  distance[s] = 0
  while False in in_tree:
    u = next_vertex(in_tree, distance)

    # Pick the closest vertex not yet in the tree. Efficiency can improve
    # if priority tree (min heap) is used
    in_tree[u] = True
    for (vertex, weight) in adj[u]:
      if not in_tree[vertex] and distance[u] + weight < distance[vertex]:
        # If the distance to the vertex using `u` is closer than it was
        # when `u` was not in the tree, update the tree
        distance[vertex] = distance[u] + weight
        parent  [vertex] = u

  return (parent, distance)

All-Pairs Shortest Path

Dijkstra gives the shortest path from a given source vertex to every vertex in graph.

All-pairs gives the shortest path between every pair of vertices in graph. This can be done running Dijkstra for each vertex: $O(n^3)$ . However, it is greedy so will not work with graphs with negative edges.

Floyd-Warshall Algorithm

DP algorithm to all-pairs. Solutions are limited to graphs without negative cycles: the sum of weights along a cycle is not negative.

Intermediate vertices: vertices between source and destination vertices. $p = (v_s,v_1,v_2, \dots,v_l,v_d)$ . Path has $l$ intermediate vertices.

Properties of Shortest Paths

Simple: no vertex repeated along the path (assuming the condition that there are no negative cycles).

Any sub-path of a shortest path is also a shortest path. If this was false, that sub-path could be used to make a shorter shortest path.

The Algorithm

$n$ vertices, $0\dots n-1$ , with $d(i,j,k)$ being the shortest distance from $i$ to $j$ if intermediate vertices are all in $0 \dots k$ .

Use recursion on $d(i,j,k)$ , using results from $d(i,j,k-1)$ :

If $k$ is an intermediate vertex on the shortest path:
- It is equivalent to joining the shortest paths from $i$ to $k$ , and from $k$ to $j$
That is, adding the lengths of $d(i,k,k-1)$ and $(k,j,k-1)$
$k$ is not an intermediate vertex: the same as $d(i,j,k-1)$

There are three base cases:

$d(i,j,k) = 0$
- When $k = -1$ and $i = j$
$d(i,j,k) = \infty$
- When $k = -1$ and $(i,j) \notin E$
- No intermediate edges, and no edges connecting $i$ and $j$
$d(i,j,k) = w((i,j))$
- No intermediate edges, and a edge connecting $i$ and $j$ : set the distance to the weight of that edge

Top-Down

All three parameters can take on $n$ values, so the size of the cache is $O(n^3)$ , and each individual call runs in constant time. Thus, the algorithm is $O(n^3)$ .

Bottom-up

Uses table of size $n\times n$ , with the columns and rows being $i$ and $j$ respectively. Initially, the table contains the weights of the edge between $i$ and $j$ , infinity if it doesn’t exist, or $0$ if $i = j$ .

Thus, the space complexity is $\Theta(n^2)$ . This works as the value of $d(i,j,k)$ is dependent only on the values of $d(i,j,k-1$ so only the $k-1$ values are needed, and the matrix can be incrementally updated.

Run the algorithm with $k=0$ , and once all cells are filled in, move on to $k=1, 2, \dots$ .

Backtracking

Technique to generate all or some solutions to a problem incrementally. Generate one possible solution, and if it isn’t correct, then use it to generate children, and repeat.

def dfs_backtrack(candidate, input, output):
  if is_solution(candidate, input):
    add_to_output(candidate, output)
  else:
    for child in children(candidate, input):
      dfs_backtrack(child, input, output)

candidate: vertex of the tree
input: information about instance of the problem i.e. desired output (e.g. size of the solution)
output: list of valid solutions
is_solution: returns true if it is a leaf node: valid solutions won’t have valid children, so there is no need to go further down the tree
children: returns list of possible candidates

In some cases such as search, only one solution may be required.

Pruning

In some cases, it may be known that it is impossible for any children (and their children etc.) of a node to produce a solution, meaning making further calls is unnecessary.

Check if pruning is required at the start of the DFS/BFS backtrack function.