Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
6 Cards in this Set
- Front
- Back
|
What's the difference between a maximal and complete matching? |
A maximal matching is where the number of arcs is as large as possible without necessarily pairing all vertices. A complete matching pairs all vertices.
|
|
|
Differences between Prim's and Kruskal's? |
Prim's builds in a connected fashion Prim's needs a start node Kruskal's lists arcs in order of weight Prim's can be done form a table |
|
|
What is an alternate path? |
A path from an unmatched vertex in one set to an unmatched vertex in the other set which alternately uses arcs not in/in the matching
|
|
|
How do you work out the number of arcs in a connected graph from nodes (n) and the sum of the degrees of all the nodes (m)? |
m/2 |
|
|
How do you work out the number of arcs in a MST of the connected graph from nodes (n) and the sum of the degrees of all the nodes (m)?
|
n-1 |
|
|
Which is a better lower bound of workers, one using the equation or one using a Gant chart and why? |
The larger one as it's larger |
