Modelling with Algorithms Flashcards
what is an optimal solution in the context of a bin packing problem?
a solution which uses the least number of bins
what are heuristic algorithms?
an algorithm that usually finds a good solution, but isn’t guaranteed to find the optimal solution
how many edges does a tree with n vertices have?
(n - 1) edges
define ‘tree’
a simply connected graph with the minimum possible number of arcs
what is a complete graph?
A simply connected graph with the maximum possible number of arcs
how many edges does a complete graph with n vertices have?
[n(n - 1) / 2 ] edges
what is a connected graph?
a graph in which every vertex is joined directly or indirectly to each of the other vertices
what is a simple graph?
a graph with no loops and no repeated edges
how do you find the order of a vertex of an undirected graph from an incidence matrix?
add together the value of the row (or column) which corresponds to that vertex
the incidence matrix of an undirected graph is ___________ about the leading diagonal
symmetrical
what complexity do Prims and Kruskal’s algorithms have?
O(n²)
if you get a non-integer solution to a graphical LP, how do you find an integer solution?
look at the 4 integer points around it, check if they’re in the feasible region and then sub them into the OBJECTIVE FUNCTION
What is a DEGENERATE problem in Linear Programming?
a problem with more than one way of finding the max value of the objective function
how do you formulate Dijkstra’s algorithm as an LP?
Minimise the objective function, which is the sum of all nodes that can be travelled - ignore nodes that go back into the source or go out of the sink
state that the variables are either 1 or 0
Look at individual nodes to work out the constraints
e.g AB + AC = 1 means that the shortest path will either take AC or AB, but not both or neither
you can only enter and leave a node once.
e.g AB + CB - BD - BC = 0
