Graphs

Question 1

What is a decision graph?

Answer 1

A model which shows a series of points and their connectivity

Question 2

Define arc and node

Answer 2

Node: the points which the graph connects, aka vertices
Arc: the connectors between nodes, aka edges

Question 3

Define a simple graph

Answer 3

A graph with no loops and only one arc connecting each node to another

Question 4

Define a connected graph

Answer 4

A graph where every node is connected to every other node, either directly or indirectly

Question 5

Define a complete graph

Answer 5

A graph where each node is connected directly to each other node once

Question 6

What is a trail?

Answer 6

A sequence of arcs such that one arc begins where the last ended

Question 7

What is a path?

Answer 7

A trail within which each node is used only once

Question 8

What is a closed trail?

Answer 8

A trail where the start and end nodes are the same

Question 9

What is a cycle?

Answer 9

A closed trail where the only repeated node is the first/ last

Question 10

What does the order of a node mean?

Answer 10

The number of arcs leaving the node

Question 11

What condition must be met for a closed trail to exist?

Answer 11

The order of every node is even or there are only two odd nodes

Question 12

What is the difference between Eulerian and Semi Eulerian graphs?

Answer 12

Eulerian has only even noes, while Semi Eulerian has two odd nodes

Question 13

What is meant if a graph is traversable?

Answer 13

Each arc is used only once, nodes may be repeated

Question 14

What are the steps of the route inspection algorithm?

Answer 14

1. Find all odd order nodes
2. for each pair of odd nodes, find the shortest connecting route between them
3. Pair the nodes such that the weight of these connecting routes is minimised
4. On the graph, duplicate these chosen paths
5. Find a trail on the new Eulerian graph

Question 15

Define a Eulerian graph

Answer 15

A connected graph where all the nodes have even orders

Question 16

Define a Semi-Eulerian graph

Answer 16

A connected graph where only 2 nodes have an odd order

Question 17

When is the route inspection algorithm used?

Answer 17

To find the route of least weight which uses each arc at least once

Question 18

What is a tree in graph terms?

Answer 18

A version of a graph which contains no cycles, i.e. there is only one route connecting any one node to any other node

Question 19

What is a spanning tree?

Answer 19

A tree where all the nodes of the original graph are used

Question 20

What transforms a graph into a network?

Answer 20

Adding weights to the arcs

Question 21

What does the weight of an arc mean?

Answer 21

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

Question 22

What do Prim’s and Kruskal’s algorithms do?

Answer 22

Find the minimum spanning tree of a network

Question 23

How do you perform Kruskal’s algorithm for a network with n nodes?

Answer 23

1. Choose the arc of least weight
2. Choose, from the remaining arcs, the one of least weight which does not create a cycle
3. Repeat until (n-1) arcs have been chosen

Question 24

How do you perform Prim’s algorithm?

Answer 24

1. Choose a starting node (Usually given in the question)
2. 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
3. Repeat until all nodes have been connected

Question 25

What is Dijkstra’s algorithm used for?

Answer 25

Finding the route of minimum weight between two given nodes

Question 26

How do you perform Dijkstra’s algorithm?

Answer 26

1. Label the starting node 1. From here, give all nodes directly connected to it a temporary label of the weight of the connecting arc.
2. Choose the arc with the smallest temporary label, and make this label permanent. Number each node with the order you have chosen them in.
3. 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.
4. Repeat 2 and 3 until you reach the end node
5. Trace the route back from the end node to find the order of the nodes which were used

Question 27

What must you remember about Dijkstra’s algorithm?

Answer 27

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

Question 28

How do you perform the Lower Bound Algorithm?

Answer 28

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

Question 29

How do you solve the Nearest Neighbour problem?

Answer 29

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

Question 30

When is the nearest neighbour problem encountered?

Answer 30

When trying to find the route of minimum weight which visits all nodes and returns to the starting node.