Combinatorial Optimisation Flashcards
We say that two vertices x and y are adjacent if
There is an edge connecting x and y
The degree of a vertex x is
the number of vertices adjacent to x
Handshaking lemma:
sum(deg(x)) = 2 |E|
^ |E| is the number of edges, I think
Adjacency matrix
A matrix with an entry 1 if x and y are adjacent and 0 otherwise.
Adjacency list
For each vertex i we keep an ordered list of its neighbours
The number of steps taken to check if two vertices are adjacent for a:
- adjacency matrix
- adjacency list
- matrix: n^2
- list: 2m
(n is number of vertices; m is number of edges)
We prefer an adjacency matrix when…
The graph is dense
If there is not a path between two vertices then we say that the distance between them is…
…infinite.
In order to find the connected components of a tree we use…
a breadth-first search.
A property of BFS trees
If xy is an edge of G not belonging to the BFS tree then either x and y are in consecutive layers or in the same layer.
Breadth-First Search
Start at some point s. Then define each layer L[i] as the set of vertices adjacent to some vertex in L[i-1] that are not already in the BFS tree.
Theorem: a graph is bipartite if and only if
it contains no odd cycle
Algorithm for testing bipartiteness
Run BFS.
Let R be the union of odd layers and B be the union of even layers.
If there are no edges connecting two red vertices or two blue vertices, the graph is bipartite.
A greedy algorithm
is one which makes locally optimal choices in the hope of finding a globally optimal choice.
Prim’s algorithm for finding an MST
Pick a vertex to start with s, and make s an element of T.
Of all the edges that connect T to vertices not in T, pick the one with the lowest weight.
Output T.
Kruskal’s algorithm for finding an MST
- Order edges in decreasing weight
- Add the lowest weight to the tree, if doing so does not produce a cycle
Cut property
Cut the network into two sections A and B. If e is the edge with minimum weight connecting A and B, then it must be part of the MSTs.
How to deal with weights when some might be the same?
Add very small perturbations to them in order to choose between them.
Interval scheduling
Always choose the event that finishes first, and remove all events incompatible with that event.
Conceptualising interval scheduling as a network probem
Make a graph having two vertices adjacent if the events overlap; then find the largest set of vertices that are mutually non-adjacent.
Interval scheduling: minimising required resources
The minimum number of resources required is equal to the maximum number of overlapping tasks.
We say that an algorithm is of O(g(n)) if
…f(n)
Worst-time complexity
The maximum number of operations on inputs of size n
Master Theorem: given the recurrence
T(n)
T(n) = O(n) if q = 1 T(n) = O(nlogn) if q = 2 T(n) = O(n^logq) if q > 2
Karatsuba’s integer multiplication: set up
write x as x = x[1] * 2 ^ n/2 + x[0].
Karatsuba’s algorithm: trick
Work out:
- x[0]*y[0]
- x[1] * y[1]
- (x[1] + x[0]) * (y[1] + y[0])
