D1 - Algorithms On Networks Flashcards
Describe how to carry out kuskals algorithm.
Sort all the arcs into ascending order f weight.
Select the arc of least weight to start the tree.
If the next arc of least weight forms a cycle ignore it, if not add it.
Repeat until all vertices are connected.
What is a minimum spanning tree?
A spanning tree such that the total length f it arcs is as small as possible.
Can be called a minimum connector.
How do you use Prims algorithm?
Choose any vertex to start the tree.
Select an arc of least weight that joins a vertex that isn’t in the tree to one that is.
Choose randomly if equal weight.
Repeat until all vertices are connected.
What algorithm is best suited to a distance matrix?
Prim’s algorithm.
How are networks inputted into computers?
As a distance matrix
How do you use Prim’s algorithm on a distance matrix?
Choose any vertex to start the tree.
Delete that row in the matrix.
Number that column in the matrix.
Put a ring around the lowest undeleted entry in the numbered columns.
The ringed entry becomes the next arc to be added to the tree.
Repeat until all the rows are deleted.
How do you use dijkstra’s algorithm?
Page 51.
What is dijkstra’s algorithm used to find?
The shortest path between two vertices in a network.
What is a graph if all the valences are even?
Eulerian.
What is the graph is precisely two valencies are odd but the rest even?
Semi eularian.
What makes a traversable graph?
If it is possible to traverse/travel along every arc just once without taking your pen from the paper.
All valencies must be even.
What makes a semi travers able graph?
If it has two odd valencies, the start and end point will be the two odd valencies.
What makes a graph not traversable?
If it has more than two odd valencies.
What is the route inspection algorithm used for?
To find the shortest route that traverses every arc at least once and returns to the starting point.
Chinese postman.
If all vertices have an even valency then the length of the shortest route will equal the weight of the network.
