Karteikarten
D1 Networks

Karten in diesem Stapel (21)
- 1MINIMUM SPANNING TREES?- smallest tree to connect all nodes
- Kruskals
- Prims
- no. of arcs for n nodes = n - 1 - 2Kruskals Alogrithm?- list all arcs smallest -> largest in weight
- choose arc w/ smallest weight
- from remaining arcs, choose the smallest, as long as it DOESN'T FORM CYCLE W/ ARCS ALREADY CHOSEN
- repeat step 3 until all nodes in/directly connected
* cross out arcs not used, tick ones used
* add up total weight if not given
* if they say you CANNOT use an arc, say 'remove (arc), add in (other arc). Then weight will go up/down by..'
* 'New MST =..' - 3Prims Alogrithm- select any node. Call it initial tree
- select shortest arc connecting the tree to a new node
- incorporate that arc and node into the tree
- repeat 2 + 3 until all nodes connected
* remember that the shortest arc may not be connected to the node you just joined! - 4Prims on a matrix?- choose start vertex, LABEL THE COLUMN corresponding with the vertex (1) and DELETE THE ROW
- look in all columns numbered so far, circle the smallest undeleted number then delete the rest of the ROW
- label column corresponding to this vertex w/ next available label then delete the row
- repeat 2 + 3 until all rows deleted
- if asked, draw MST w/ all the circled points - 5SHORTEST ROUTE?- Dijkstras
- sometimes ask for shortest trail - 6Dijkstras Algorithm label?

- 7Dijkstras Algorithm?- give start node permanent label of 0 and order 1
- give every node connected to the start node a temporary label by recording it's distance from the START
- find the smallest temporary label of WHOLE NETWORK and make this label permanent
- update temporary labels for any node that can be reached DIRECTLY from most recent permanent node if distance is less than temp. label
- repeat 3 + 4 until the destination node has been given a permanent label
-Go backwards through the network, retracing the path of shortest length from the
destination node to the start node - 8Algebraic Network Questions?- still use Dijkstras
-Q will usually give algebraic function a limit so that you know it'll be bigger/smaller than another node/arc
- can use simultaneous equations if it comes up
LOOK IN BOOKLET FOR EXAMPLES - 9What are Route Inspection Problems used for?to find the shortest closed trail
- 10What if the graph is Eulerian?every node is even, so total weight of route is total weight of network
- 11What if the graph is Semi - Eulerian?(exactly 2 odd nodes)
- add up whole network
- add up shortest trail from first odd node to second
- add together - 12What do you use for a graph that has more than one pair of odd nodes?Chinese Postman
- 13Explain this algorithm?1) list odd ordered nodes
2) list possible pairings and their weights when getting from one to other (e.g. AB + CD -> 4 + 5 = 9)
3) choose smallest weight
4) shortest closed trail = total weight of tree + smallest weight you just picked - 14Any extra questions they can ask?LOOK IN BOOKLET
- 15What are Travelling Salesperson problems?finding shortest cycle which lists every node exactly once and returns to the start
- 16What are these cycles called?Hamiltonian Cycles
- 17How do you find the Upper Bound?Nearest Neighbour
- 18Describe Nearest Neighbour?- choose any node
- from nodes not already selected, find nearest node to last
- repeat until all nodes selected
- join last node to first node directly if possible (or if not by the shortest route) - 19What are the problems with Nearest Neighbour?- greedy algorithm: best short term solution but poor choices for last few arcs
- sometimes it gets stuck if graph isn't complete - 20How do you find the Lower Bound?- choose a node as 'special node' and delete it + all arcs connected to it
- find MST for remaining arcs/nodes
- add in the two smallest arcs connected to the 'special node' - 21Is there a Solution?No, not exactly, the optimal solution will be between the LB and UB (put as <= not <)
Informationen
- Beschreibung
- A level Maths (D1) Karteikarten am D1 Networks, erstellt von Maisie Carroll am 15/03/2017.
- Erstellt von
- Maisie Carroll
- Aufrufe
- 1
- Bewertung
Mehr zu Graph and Network Algorithms