Why is it not possible to find a complete matching?
X is the only element that can be matched to Y and Z
1 of 19
Define 'alternating path'
A path from an unmatched vertex in one set to an unmatched vertex in the other which uses arcs that not in/in the matching
2 of 19
Define 'matching'
A one-to-one pairing of some of the elements in one set to some of the elements in the other set
3 of 19
Why does the matching algorithm need to be applied twice?
There are two unmatched vertices in each set and the algorithm can only match one on each side per iterations
4 of 19
Define 'bipartite graph'
A graph consisting of two distinct sets of vertices X and Y in which arcs can only join a vertex in X to a vertex in Y
5 of 19
Define 'complete matching'
A one-to-one matching between all elements of X onto Y
6 of 19
Explain how you determined the quickest route from your labelled Dijkstra's diagram?
Trace back from the final vertex. Include arc XY if the difference in the final values of X and Y equals the arc length
7 of 19
Explain what is meant by the term 'path'
A finite sequence of edges, such that the end vertex of one edge is the start of the next and in which no vertex appears more than once
8 of 19
Is the Dijkstra route unique?
Is another route / Isn't another route so isn't/is unique (provide other route if possible)
9 of 19
Given that certain footpaths are already in place between certain vertices, which algorithm would be used to find the tree and how would it be adapted?
Start tree with given arcs then apply Kruskal's
10 of 19
Give differences between Kruskal's and Prim's
P starts with any vertex/K starts with the shortest arc, Don't need to check for cycles using P, P adds nodes/K adds arcs, Tree grows in connected way using P, P can be used in matrix form
11 of 19
Define 'tree'
Connected graph with no loops, cycles or multiple edges
12 of 19
Define 'spanning tree'
A tree that includes all vertices
13 of 19
Define 'minimum spanning tree'
A spanning tree of minimal total length
14 of 19
How will new path affect the total length of the route in route inspection
New path would make certain vertices have even degree but certain paths must still be traversed twice
15 of 19
Determine starting and finishing point for the route if it can start and end at different vertices
Repeat smallest path so start and finish at the remaining vertices
16 of 19
Explain why a network cannot have an odd number of vertices of odd degree
Each edge contributes 2 to the sum of degrees, so this sum must be even. Therefore there must be an even (or zero) number of vertices of odd degree. Hence there cannot be an odd number.
17 of 19
Is the route unique?
If it is not, give another route
18 of 19
If each arc must be traversed twice, how does this differ from the original algorithm?
Each arc has to be traversed twice
19 of 19
Other cards in this set
Card 2
Front
Define 'alternating path'
Back
A path from an unmatched vertex in one set to an unmatched vertex in the other which uses arcs that not in/in the matching
Card 3
Front
Define 'matching'
Back
Card 4
Front
Why does the matching algorithm need to be applied twice?
Comments
No comments have yet been made