10_Graph theory and network flow problems Flashcards
1
Q
Directed Graph
A
G = (V,A,c)
- is made of a set of nodes V
- and set of arcs A (i,j)
- weights of arcs denoted as c(ij)
2
Q
Undirected Graph
A
G = [V,A,c]
- is made of a set of nodes V and a set of edges A
- an edge [i,j] is defined by the 2 nodes i and j
- edges have costs c
3
Q
Dijkstra Algorithm
Prerequisites
A
- directed or undirected graph
- graph cannot have cycles
- no negative weights
4
Q
Floyd Warshall Algorithm
Prerequisites
A
- weights can be negative
- graph can have cycles
5
Q
How to determine shortest path with Floyd-Warshall-Algorithm
A
- shortes path from node i to j
- D(16) = 6
- p(1,2) = 1
- p (2,5) = 2
p = predecessor
6
Q
Avoid Mistake with Floyd-Warshall-Algorithm
A
- check whether a node below current iteration node is changed
7
Q
Methods for Graph Theory
A
- Dijkstra’s Algorithm
- Floyd-Warshall Algorithm
- Minimum Spanning Tree Problem
8
Q
Network Flow Problems
Methods
A
- solving Maximum Flow Problem with Ford-Fulkerson Algorithm
9
Q
How to determine Minimum Cut in Ford-Fulkerson Algorithm
A
- using last iteration when algorithm stopped
- anything in last column will be in V(q) anything else in V(s)
- Capacity K: maximum outflows - minimum inflows
10
Q
Minimum Spanning Tree Problem
* Prerequisites
* Procedure
A
Prerequisites
- undirectd graph with edge weights
Procedure
- determine list of undirected edges starting with smallest weight in ascending order
- stop algorithm at n-1
- add edges to graph so that it doesnt have a cycle
