Combinatorial optimization problems
9 important questions on Combinatorial optimization problems
Give the approach for the Hungarian method
- Find the minimum in each row;
- Substract the minimum from each value in each row;
- Find the minimum in each column;
- Substract the minimum from each value in the column;
Step 2
- Draw a minimum number of lines needed to cover all the zeros;
- m lines required? Optimum solution is found among the 0's
- <m lines? Continue step 3
Step 3
- Find the smallest non zero element not covered by lines k;
- Substract k from each uncovered element;
- Add k to each element that is covered by 2 lines;
- Go back to step 2;
Give the steps to execute MST
- Begin at note i
- Connect it to the closest not j
- C(i,j)
- remaining notes C'
Step 2
- Choose a member from C' closest to C call it n
- C(i,j,n)
- C'= C'-n
Step 3
- repeat
Constantly check the thing as a whole!
In MST what do the following represent?
- V
- G
- E
- G'
- V Vertices of a graph
- G Items we wish to connect
- E items that can be directly linked
- G' Spanning tree since removing one vertex does not reduce connectivity
- Higher grades + faster learning
- Never study anything twice
- 100% sure, 100% understanding
How can you prevent cycling in MST?
- Sum Xij = n-1
- sum xij = |V'| - 1
What is the difference between MST and TSP?
In TSP what is
- tour
- symmetric
- Assymetric
any route visiting each city once;
symmetric
dij = dji
Assymetric
dij is not dji
In TSP what are the subset elemination constraints? [2]
3 =< |S| =< |V| -3
What is ocnsidered to be a tree?
In graph C.O.P. (Combinatorial Optimization Problem) graph theory what are theorems?
A graph is a tree when there is exactly one path between each pair of vertices;
Theorem 2
A tree with n vertices has n-1 edges;
Theorem 3
Any connected graph with n vertices and n-1 edges is a tree;
Theorem 4
A graph is minimally connected when removal of any edge disconnects the graph;
Theorem 5
A graph is a tree only when it is minimally connected;
The question on the page originate from the summary of the following study material:
- A unique study and practice tool
- Never study anything twice again
- Get the grades you hope for
- 100% sure, 100% understanding
![Trustpilot Logo](/images/design_2020/lp/clp-trustpilot-en.png)