Graphs

Definitions #

• Degree of a node: the number of edges connected to it
• Connected graph: there is a path between any two nodes
• Weighted graph: every edge has a weight
• Euler paths/cycles
  • Euler path: a path that visists every edge of a graph exactly once
  • Euler cycle: an Euler path that starts and ends at the same vertex
  • A connected graph has an Euler cycle if and only if all nodes have an even degree
  • A connected graph has an Euler path if at most two nodes have an odd degree
• Simplicity
  • Simple path: when all nodes are different
  • Simple cycle: when all nodes are different (execpt begin/end) and it contains at least 3 nodes
  • Simple graph: when it contains no loops and no paralel edges
• Trees as graphs
  • A tree is a connected simple graph without simple cycles
  • Spanning tree: a full subgraph that is a tree
  • Minimal spanning tree: an undirected spanning tree for which the weight is minimal

Depth-First Search (DFS) #

Keep exploring if we can (greedy) and backtrack if we cannot go further.

dfs(v, G):
    add v to visited
    set discovery time of v
    for all e neighour edges of v:
        w = other node of e
        if v is not visted:
            dfs(, G)
    set finished time of v

for each v in G:
    visited = empty set
    if not v is visited
        dfs(v, G)

Keeps track of discovery & finished time which can be used by other algorithms

Breath First Search (BFS) #

Discovers new nodes step-by-step & finds shortest path in an unweighted graph.

bfs(v, G):
    Q := empty queue
    visited := empty set
    Q.enqueue(v)
    while Q is not empty:
        u := Q.dequeue()
        for all neighours edges of u:
            w := other node of e
            if w is not visited:
                visited.add(w)
                Q.enqueue(w)

DFS vs BFS #

Let $m$ the number of edges and $n$ the number of nodes in a graph:

Dijkstra's Algorithm #

Computes the shortest path from any node to all other nodes (greedy). Uses a priority queue (implemented as heap) to get the next node with the minimal distance.

dijkstra(v, G)
    parent := parent nodes in shortest path tree
    dist := array of distances
    Q := priority queue with all the nodes
    for all nodes u in G:
        dist[u] := u=v ? 0 : infinity
    while Q is not empty do:
        u := Q.removeMin()
        for all neighbours w of v:
            new_dist := dist[u] + dist[u][w]
            if new_dist < d[w]:
                dist[w] = new_dist
                parent[w] = u
                Q.decreasePriority(w, new_dist)

The parent array can be backtracked to find the shortest path between two vertices.

Time complexity #

Let $m$ the number of edges and $n$ the number of nodes in a graph:

• Every node is enqueue'd and removeMin'd once
• Every node $v$ has its priority decreased at most $degree(v)$ times
• The sum of all degrees is $2m$
• Each action (enqueue/removeMin/decreasePriority) takes $\mathcal{O}(\log{(n)})$ time

Conclusion: the time complexity for Dijkstra's algorithm is: $\mathcal{O}((n+m)\log{(n)})$

A* algorithm #

Uses a heuristic such that less nodes of the graph have to be traversed. Often the distance between locations is used.

Floyd-Warshall #

First construct a $n \times n$ matrix $W^0$ where $n$ is the number of nodes in the graph:

• Every edge from node $a$ to node $b$ with weight $w$ is $W_{a,b} = w$
• $0$ on all self loops, $W_{i,i} = 0$ for all $0<i < n$
• The rest is $\infty$

Then iterate $k$ from $1$ to $n$:

$$ W_{i,j}^k = \min\{ W_{i,j}^{k-1}, W_{i,k}^{k-1} + W_{k,j}^{k-1} \} $$

Ford-Fulkerson method #

Finds the maximum flow in a directed graph form the source $s$ to the sink $t$.

• Augmenting path: a path of edges in the residual with a unused capacity greater than zero
• Time complexity: $O(Ef)$

First, make the residual graph by adding all residual edges in the reversed directions of the existing edges with a flow and capacity of 0 (anti-parallel edges are disallowed). The other edges start with a flow of 0.

While there is a augmented path:

1. Find the bottleneck the edge in the path with the minimal capacity
2. Augment (update) the flow of the edges in the path. On forward edges increase the flow by the bottleneck. And on residual edges decrease the flow by the bottleneck

The maximum flow is the sum of all the bottleneck values.

This is just the method, an actual algorithm is for example the Edmonds–Karp algorithm which uses BFS and runs in $O(VE^2)$.