Networks Flashcards
What is a tour?
A closed route that passes through each node at least once.
What is a network?
A weighted graph.
Vertices are called nodes.
Edges are called arcs.
Arcs can be directed or undirected.
What kinds of network can be represented as a weighted matrix?
Simple networks (networks formed of a simple graph).
What is a spanning tree?
A tree that connects all the nodes in a network.
What is the MST?
Minimum spanning tree.
The spanning tree with the least total weight.
What is the aim of the Chinese postman problem?
To find the least weight route that uses every arc of a network.
(imagine a postman trying to travel along every road in the minimum time)
What is the aim of the travelling salesperson problem?
To find the least weight hamiltonian cycle.
imagine a salesperson trying to get to each house in the minimum time possible, without travelling down any road twice
How can the Chinese postman problem be solved?
If the network is formed by a eulerian graph, the probelm is already solved.
If not, the network must be altered so it becomes eulerian, by connecting all odd degree nodes to make them even, using the least weight possible. (list out all odd degree nodes)
How can an upper bound for the travelling salesperson problem be found?
Using the nearest neighbour algorithm.
How can a lower bound for the travelling salesperson problem be found?
Remove a node and all its connected arcs.
Construct an MST for the remaining network.
Add the weight of this MST to the two least weight arcs reconnecting the removed node.
What are the two methods used to find an MST?
Kruskal’s algorithm
Prim’s algorithm
What is Kruskal’s algorithm to find an MST?
List all arcs in increasing order of weight.
Add an arc of minimum weight to the tree so that no cycles are created.
Repeat this step until a spanning tree is obtained.
What is Prim’s algorithm to find an MST?
Start with a node usually stated in the question.
Add a minimum weight arc joining a node already included to a node not yet included.
Repeat this step until a spanning tree is obtained.
(there may be multiple MST’s)
-this process can easily be done in tabular form
