Trees/Paths/Flows Flashcards
Name the condition under which Dijkstra’s algorithm correctly determines the shortest path between a starting vertex and all other vertices in a graph
Where none of the edges have negative edge weights
What algorithm can find the shortest path even despite negative weights?
Algorithms like the Bellman-Ford Algorithm
What is a spanning forest?
a spanning forest of a graph is family of subgraphs such that each subgraph is a tree, the trees don’t overlap and every vertex in the spanning forest is contained in a tree
What does vertex disjoint mean?
Two trees that are vertex disjoint don’t overlap
How many vertices must a spanning tree have to be considered a tree?
What must a graph be to be considered a tree?
1 or more vertices
it must be acyclic (must not contain cycles)
What is a spanning tree?
a spanning tree is a spanning forest consisting of a single tree.
Does Ford’s algorithm always terminate?
No if the graph contains cycles with edges with negative weights
What is a vertex cut?
Partitions a graph into two non-empty sets
What is a crossing edge?
The edge that joins two sets, by connecting a vertex in one set to a vertex in another set
What is the cut property?
- provides criteria for selecting edges in the MST
- For any vertex cut, the crossing edge between the sets with the most minimum weight is in the MST
What are the steps in Prim’s algorithm to find the MST:
1) Start at a random vertex
2) add the edge with the smallest weight to the MST
3) move to the next vertex, do the same
4) if adding the edge with the smallest weight will create a cycle, don’t add it and add the edge with the next smallest weight
5) repeat until we have n-1 edges, for n vertices.
Why does Prim’s algorithm work
- We start from a spanning forest where every vertex is its own tree.
- We start at a vertex and keep picking the minimum edge to add to our tree.
- Adding an edge from the spanning forest won’t cause an error, as we only add it if it won’t cause a cycle, so we keep doing this until we have n-1 edges, for n vertices.
What are the steps in Kruskal’s algorithm to find the MST:
1) order edges by ascending order of edge weight
2) initialise tree as empty
3) go through list of edges adding the edge to tree as long as it doesn’t cause a cycle
4) return the tree
Why does Kruskal’s algorithm work
- Initially our graph holds trivial trees (made of 1 vertex each).
- Whenever we add an edge we connect two trees.
- If we add an edge with the current most minimum weight, until we can’t add anymore edges without creating a cycle, we will have a spanning tree with all the smallest weights.
How do we encode a graph problem?
xe for each e ∈ E (decision variable for each edge)
objective is maximise or minimise either weight times edge or just whether to include the edge
constraints: each edge should be 0 or 1, so xe ∈ {0,1}
and flow constraints should hold, how many times each edge should be in set.
What is LP relaxation:
Relaxing the constraints of an ILP to change the problem into an LP, so it’s easier to solve
What are ILP?
Integer linear programs are where the decision variables must be integers, so only integer solutions are allowed
What is the convex hull?
The convex hull conv(S) of a set S ∈ R^n consists of all the convex combinations of points in S
When is a convex set integral?
If the convex hull of it’s integer points is the same as the set itself
What ILP constraint says the entire graph edges should sum to 1 less than the number of vertices?
Sum of xe for e ∈ E = |V| - 1 where V is the set of all vertices
What ILP constraint says the all subsets of vertices should not contain any cycles?
- They should contain vertices in subsets-1 edges for subsets that aren’t empty and aren’t V:
Sum of xe for e ∈ S <= |S|-1 for ∅ ⊂ S ⊂ V
How can we prove we have the optimal solution for an ILP:
- By constructing the dual of the ILP encoding and relaxing it, by strong duality, it will show the primal ILP is optimal
- or show that complementary slackness holds for the dual
When is a digraph considered simple?
If it has no loops (cycles) or parallel arcs
What is the definition of a feasible potential
What does a feasible potential provide?
The lower bound for the shortest path costs
What constraint says we want incoming edges - outgoing edges = 0 for every vertex except the source and the sink:
Sum of xuv (u,v) ∈ E - Sum of xvw, (v,w) ∈ E = 0 for v ∈ V \ {S, T}
For an ILP graph problem what do we assume to get an optimal solution?
That the edges weights are all non-negative
What ILP constraint says we want the total of outgoing edges to be 1 for the source?
Sum of xsv = 1, (s,v) ∈ E
What ILP constraint says we want the total of incoming edges to be 1 for the target?
Sum of xvt = 1, (v,t) ∈ E
What does it mean if there’s a negative cost cycle in the graph:
Then the LP is unbounded
What condition tells us which edges we need to take for the shortest path?
The feasible potential
What is true if u is not a feasible potential after n-1 iterations:
There is a negative cost cycle
In the min-flow max cut problem, what must there be for the flow to be improved?
There must be an augmenting path (a path where there is still flow left)
What is a residual network?
It shows flow that is leftover along edges (where there is flow remaining that can be pushed along an edge)
what condition proves that the dual of the max flow min cut problem gives an optimal solution?
Total unimodularity
