Graphs Flashcards
What is a decision graph?
A model which shows a series of points and their connectivity
Define arc and node
Node: the points which the graph connects, aka vertices
Arc: the connectors between nodes, aka edges
Define a simple graph
A graph with no loops and only one arc connecting each node to another
Define a connected graph
A graph where every node is connected to every other node, either directly or indirectly
Define a complete graph
A graph where each node is connected directly to each other node once
What is a trail?
A sequence of arcs such that one arc begins where the last ended
What is a path?
A trail within which each node is used only once
What is a closed trail?
A trail where the start and end nodes are the same
What is a cycle?
A closed trail where the only repeated node is the first/ last
What does the order of a node mean?
The number of arcs leaving the node
What condition must be met for a closed trail to exist?
The order of every node is even or there are only two odd nodes
What is the difference between Eulerian and Semi Eulerian graphs?
Eulerian has only even noes, while Semi Eulerian has two odd nodes
What is meant if a graph is traversable?
Each arc is used only once, nodes may be repeated
What are the steps of the route inspection algorithm?
- Find all odd order nodes
- for each pair of odd nodes, find the shortest connecting route between them
- Pair the nodes such that the weight of these connecting routes is minimised
- On the graph, duplicate these chosen paths
- Find a trail on the new Eulerian graph
Define a Eulerian graph
A connected graph where all the nodes have even orders
Define a Semi-Eulerian graph
A connected graph where only 2 nodes have an odd order
When is the route inspection algorithm used?
To find the route of least weight which uses each arc at least once
What is a tree in graph terms?
A version of a graph which contains no cycles, i.e. there is only one route connecting any one node to any other node
What is a spanning tree?
A tree where all the nodes of the original graph are used
What transforms a graph into a network?
Adding weights to the arcs
What does the weight of an arc mean?
It represents a value such as distance or the number of houses on a street etc. It is used when finding a route which either minimises or maximises the total value
What do Prim’s and Kruskal’s algorithms do?
Find the minimum spanning tree of a network
How do you perform Kruskal’s algorithm for a network with n nodes?
- Choose the arc of least weight
- Choose, from the remaining arcs, the one of least weight which does not create a cycle
- Repeat until (n-1) arcs have been chosen
How do you perform Prim’s algorithm?
- Choose a starting node (Usually given in the question)
- Choose the arc of least weight connecting to any nodes you have chosen which does not create a cycle and choose the node this links to the tree
- Repeat until all nodes have been connected
What is Dijkstra’s algorithm used for?
Finding the route of minimum weight between two given nodes
How do you perform Dijkstra’s algorithm?
- Label the starting node 1. From here, give all nodes directly connected to it a temporary label of the weight of the connecting arc.
- Choose the arc with the smallest temporary label, and make this label permanent. Number each node with the order you have chosen them in.
- Inspect all node that can now be reached. If there is a new shortest route to that node, replace the temporary label. If not, leave as is.
- Repeat 2 and 3 until you reach the end node
- Trace the route back from the end node to find the order of the nodes which were used
What must you remember about Dijkstra’s algorithm?
When choosing the next node, choose the smallest temporary label on the whole graph, not just nodes connected to the last one to become permanent
How do you perform the Lower Bound Algorithm?
Step 1: Choose any node, X, and find total of the two smallest weights converging at X
Step 2: Remove X and all connected arcs. Find the new minimum connection (Kruscal’s)
Step 3: The sum of these two totals is the lower bound
How do you solve the Nearest Neighbour problem?
Find a minimum connector to be the upper bound. Perform the lower bound algorithm to find the lower bound. Adjust the starting nodes to find the smallest upper bound and the largest lower bound. The resulting range must contain the answer
When is the nearest neighbour problem encountered?
When trying to find the route of minimum weight which visits all nodes and returns to the starting node.
