# 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:

DFS | BFS | |
---|---|---|

time complexity | $\mathcal{O}(m+n)$ | $\mathcal{O}(m+n)$ |

finds shortest path | No | Yes |

good for infinite graphs | No | Yes |

needs memory for | current branch | whole level (queue of nodes) |

## 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:

- Find the
**bottleneck**the edge in the path with the minimal capacity - 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)$.