Networks Flashcards
Vocabulary/language, minimum connector problems, route inspection problems and the travelling salesperson problem.
A network is…
a weighted graph.
A minimum spanning tree is…
a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight (i.e. a tree that minimises the weights of the edges of said tree).
List three methods for finding a minimum spanning tree:
> Remove arcs in order of decreasing weights/select arcs in order of decreasing weight.
Apply Prim’s algorithm.
Apply Kruskal’s algorithm.
Describe Prim’s algorithm.
- Start at any vertex and choose the edge of least weight that is connected to it.
- Choose the edge of least weight that is connected to any of the vertices already connected, and does not connect to another vertex that is already in the tree.
(If there is a choice of the edges of equal weight, either can be selected) - Repeat STEP 2 until all of the vertices are added to the tree.
*Cycles are avoided by only adding edges that are not already connected at one end.
Describe Kruskal’s algorithm.
- Sort the edges in terms of increasing weight.
- Select the edge of least weight (if there is more than one edge of the same weight, either may be used).
- Select the next edge of least weight that has not already been chosen and add it to your tree provided that it does not make a cycle with any of the previously selected edges.
- Repeat STEP 3 until all of the vertices in the graph are connected.
What is the difference between Prim’s algorithm and Kruskal’s algorithm?
Prim’s algorithm selects a root vertex to begin from and then traverses from vertex to vertex. Whereas, Kruskal’s selects weighted arcs starting from the arc with the lowest weight.
The number of edges in a minimum spanning tree will always be…
one less than the number of vertices in the graph.
A minimum spanning tree cannot contain…
any cycles.
The Chinese postman/route inspection problem finds…
the shortest route that covers all of the arcs at least once, returning to the start if required.
For the Chinese postman/route inspection problem to be solved a network needs to fulfil one of these three conditions:
> Eulerian if they have no odd nodes.
semi-Eulerian if they have two odd nodes.
neither Eulerian or semi-Eulerian if they have four or more odd nodes.
What is the difference between the Chinese postman/route inspection problem and the travelling salesperson problem?
The travelling salesman problem can not visit a node more than once. The path produced will consist of all different nodes/cities. The Chinese postman/route inspection problem can have duplicate nodes in the path produced (but not duplicate edges).
The travelling salesperson problem…
finds the shortest route that visits all of the nodes of a networks at least once, returning to the start.
The nearest neighbour algorithm is…
a systematic way of finding the upper bound for the minimum weight Hamiltonian cycle.
In the classical travelling salesman problem the following conditions are observed:
> the graph is complete.
the direct route between two vertices is the shortest route.
What are the steps of the nearest neighbour algorithm?
- Choose a starting vertex.
- Follow the edge of least weight from the current vertex to an adjacent unvisited vertex (if there is more than one edge of least weight pick one at random).
- Repeat STEP 2 until all vertices have been visited.
- Add the final edge to return to the starting vertex.
