Notes - DAA HT23, Graphs
Flashcards
What is the formal definition of a graph?
A pair $(V, E)$ with $V$ being a set of nodes/vertices and a set of ordered pairs $(u, v) \in E \subseteq V \times V$ representing a connection from $u$ to $v$.
Suppose we have an adjacency matrix $E$ where $E[i, j] = 1$ if there is a path from node $i$ to node $j$. What is the interpretation of $E^2$, the adjacency matrix squared?
$E[i, j]$ contains the number of walks of length 2 from $i$ to $j$.
Suppose we have an adjacency matrix $E$ where $E[i, j] = 1$ if there is a path from node $i$ to node $j$. How could you calculate the matrix giving the number of walks of at most length $k$ from $i$ to $j$?
What is the transitive closure of a graph?
The matrix where $A[i, j]$ is 1 if there is a path from $i$ to $j$, and 0 otherwise.
Can you quickly prove that if a graph has no odd length cycle then it is bipartite?
If a graph has only one vertex, it is bipartite. Otherwise start at vertex $u$ and colour all its neighbours blue. Then colour all of those neighbours red, and repeat this until you have a colouring of all vertices. No vertices can change colour during this process, because otherwise there would exist an even length path and an odd length path to the same vertex. The combination of these two paths would be an odd length cycle, a contradiction.
Programs
Program an implementation of depth-first search, outputting three arrays
- $d[v]$, the discovery time of a vertex
- $f[v]$, the finishing time of a vertex
- $\pi[v]$, the predecessor of a vertex
Todo.
Program an implementation of breadth-first search, outputting two arrays:
- $d[v]$, the distance from the start vertex to the next vertex
- $\pi[v]$, the predecessor of a vertex on the shortest path
Todo.
Program an implementation of Dijkstra’s algorithm, outputting two arrays:
- $d[v]$, the distance from the start vertex to the given vertex
- $\pi[v]$, the predecessor of a vertex on the shortest path
Todo.
Program an implementation of the Bellman-Ford algorithm, outputting:
- A boolean if it contains a negative-weight cycle reachable from the start vertex
- $d[v]$, the distance from the start vertex to the given vertex
- $\pi[v]$, the predecessor of a vertex on the shortest path
Todo.
Program an implementation of the Floyd-Marshall algorithm for solving the all-pairs shortest path problem with no negative-weight cycles, outputting two multidimensional arrays:
- $d[u, v]$, the shortest distance between arrays $u$ and $v$.
- $\pi[u, v]$, the predecessor of $u$ on the shortest path to $v$.
Todo.
Program an algorithm for determining if a graph contains a cycle, and if it doesn’t, outputs a topological sort of the vertices.
Todo.
Implement a disjoint-set data structure and use it to program Kruskal’s algorithm for finding a minimum spanning tree, and then implement Prim’s algorithm for finding achieving the same task.
Todo.