Decision 2

?
Euler's handshaking lemma
The total of the orders of nodes is x2 the number of arcs
1 of 19
Consequence of Euler's lemma
Cannot be an odd number of odd nodes
2 of 19
Bubble sort: max number of comparisons/ swaps
1/2n(n-1)
3 of 19
Connected graph: order of nodes
>1
4 of 19
Eulerian: order of nodes
All even & connected
5 of 19
Semi- Eulerian: order of nodes
1 pair of odd nodes
6 of 19
Tree: number of arcs
n-1
7 of 19
Kn: number of arcs
1/2n(n-1)
8 of 19
MST: number of arcs
n-1
9 of 19
Kruskal's
Arcs
10 of 19
Prim's
Nodes, matrix
11 of 19
Number of times a node is visited
Order of node/2
12 of 19
Graphs which cannot be planar
K5 , K3,3
13 of 19
When to apply planarity algorithm
Graph contains a Hamiltonian cycle
14 of 19
Floyd's v Dijkstra's
Floyd's finds the shortest path between any pair of nodes
15 of 19
When is the optimal solution
Biggest lower bound < optimal < smallest upper bound
16 of 19
Critical activities: float
0
17 of 19
Choosing pivot column
Smallest number in P row
18 of 19
Ratio test
Value / Pivot column number, must be smallest
19 of 19

Other cards in this set

Card 2

Front

Cannot be an odd number of odd nodes

Back

Consequence of Euler's lemma

1/2n(n-1)

>1

Card 5

Front

All even & connected

Similar Further Maths resources:

See all Further Maths resources »See all Rules resources »