Discrete Mathematics - Networks Flashcards
Define Spanning tree
A sub graph that is a tree containing every vertex in the graph
How many edges will a spanning tree with n vertices have
n-1
What is a network
A weighted graph
What does the Minimum Spanning Tree represent
The spanning tree with the least weight
What is the Kruskal’s Algorithm used for
To find the MST
Describe the Kruskal’s Algorithm Process
1- List the edges in ascending weight order
2 - Choose the arc with the minimum weight
3 - Repeat step 2 whilst avoiding those that form a cycle and until all nodes have been connected
What is the Prim’s Algorithm used for
To find the MST
Describe the Prim’s Algorithm Process
- Choose any node at random
- Choose the arc of the minimum weight joining a connected node to an unconnected node
- Repeat until all nodes are connected
What is the Chinese Postman Problem used for
To find the shortest route that travelsat least once along each arc and returns to the starting point. This is an eulerian problem and can be solved using those principles.
How is the CPP or Route Inspection Problem, solved when Eulerian and Non-Eularian
Eulerian - The distance will be the sum of the arc weights
Non-Eulerian -
1 - Identify the odd nodes
2 - List all of the possible pairings between these nodes
3 - For each pairing find the shortest route between the nodes
4 - Choose the pairing with the smallest weigh to add, and add their weigths to the original weight
What is the travelling salesperson objective
To find a hamiltonian cycle (no repeated vertices, visits each vertex once and starts and ends at the same vertex.However the bigger the graph the more the possible cycles, this mean we need a bound to determine where the correct tour lies in
How do you find the upper bound of the network
Use the Nearest neighbor algorithm:
1 - Choose a starting point
2 - Select the arc with the least weight connecting to that arc
3 - Repeat step 2 until all vertices have been connected ensuring you don’t go backwards
4 - join the last vertex to the first
optimal tour <= least upper bound
How do you find the lower bound
1 - choose a vertex and remove 2 of its least weighted arcs
2 - find the MST of that residual set
3 - add the deleted arcs weight
If when finding the lower bound you find a cycle you’ve found the optimal tour
What is the interval for the optimal tour
LB <= OT <= UB
