D1 Flashcards
(34 cards)
How do you solve a problem containing Kruskals Algorithm?
- List all arcs in size order
- Fill in in order
- Do not form loops
How do you solve a problem containing Prims Algorithm?
- Select a node
- Find smallest connecting
- Keep going until all nodes have been joined
- No loops
How do you solve a problem containing Dijkstras Algorithm?
- Pick a node
- Give nodes connecting a temporary label
- Make smallest permanent
- Repeat
How do you solve a problem containing Chinese Postman Algorithm?
- Find all odd nodes
- Connect two smallest connections and connect if Eularian
- If semi-eulerian is required leave two odd
When would you need to use the Chinese Postman algorithm?
When you need to go along every arc
How do you solve a problem containing Travelling Salesperson Algorithm?
- Find upper bound by nearest neighbour
- Find lower bound
- Put in an inequality
How do you find the upper bound for travelling salesperson?
Use nearest neighbour:
- Pick node
- Find smallest connecter
- Join all smallest until back to first node
- Algorithm fails if cannot return to first
- To find best do for all nodes
How do you find the lower bound for travelling salesperson?
- Choose a node
- Find MST
- Add node back in by drawing back the two connecting arcs with the lowest weights
What are the 8 rules of graphs?
- Total order of nodes is twice the number of arcs (so total order must be even)
- There cannot be an odd number of odd nodes
- For a connected graph, the order of each node must be at least 1
- For a simple graph with n nodes, the order of each node must not be bigger than n-1
- An Eulerian graph has all even nodes
- A semi-Eulerian graph has exactly 2 odd nodes
- Any tree with n nodes must have exactly n-1 arcs
- Kn with n nodes will have a total of 1/2n(n-1) arcs.
How do you solve a problem containing the first fit Algorithm?
- Put into first available bin in order given
How do you solve a problem containing the first fit decreasing Algorithm?
- Sort into decreasing order
- Apply first fit
How do you solve a problem containing the shuttle sort Algorithm?
- Compare first 2 numbers and swap is necessary
- Underline first number
- Compare first two numbers not underlined
- Swap with underlined if necessary
- Repeat 2-3
How do you solve a problem containing the bubble sort Algorithm?
- Compare first 2 numbers
- Take top number to end swapping if necessary
- Highest number now in place
- Underline last number
- Repeat 1-3
- Do not compare underlined numbers
How do you solve order of algorithm questions if the algorithm is of quadratic order?
- Write info given
- Work out scaling factor
- x unknown link by scaling factor squared
How do you solve order of algorithm questions if the algorithm is of cubic order?
- Write info given
- Work out scaling factor
- x unknown link by scaling factor cubed
How do you solve order of algorithm questions if the algorithm is of exponential order?
- T directly proportional to exponential given
- T = K x exponential given
- Work out K
- Put K into unknown equation
When would you need travelling salesperson algorithm?
When you need to visit every town but not every arc
Define graph
A set of vertices, or nodes which may or may not be connected by arcs or edges
Define connected graph
One in which it is possible to get from any node to any other node either directly or indirectly
Define simple graph
There is never more than one arc joining a pair of nodes and no loops joining a node to itself
Define a simply connected graph
A graph that is both simple and connected
Define a planar graph
One the can be drawn so that no arcs cross over (except for at nodes)
Define a complete graph
A simply connected graph in which every pair is connected. It has 1/2n (n-1) arcs.
What is the order of a node?
The number of arcs that are connected to the node
