Graph Theory (DP IB Applications & Interpretation (AI))

A spanning tree is a graph that contains all the vertices from a graph G and in which any two vertices are connected by exactly one path.

An adjacency matrix is a square matrix that can be used to show the number of direct connections between two vertices in a graph.

In an adjacency matrix for a graph, an entry of 0 indicates that there is no direct connection between the vertices indicated by corresponding row and column.

False.

A directed graph will not be symmetrical about the leading diagonal.

However, an undirected graph will be symmetrical about the leading diagonal.

A loop indicated in the adjacency matrix of a graph by an entry along the leading diagonal.

An entry of 1 in the leading diagonal indicates a loop in a directed graph.

An entry of 2 in the leading diagonal indicates a loop in an undirected graph.

False.

In a graph, the sum of the entries in a row is not the out degree of that vertex.

The sum of the entries in a row is the in degree of that vertex.

The sum of the entries in a column is the out degree of that vertex.

A walk is a sequence of vertices that are visited when moving through a graph along its edges.

Both edges and vertices can be revisited in a walk.

If M denotes the adjacency matrix of a graph, then the (i, j) entry in the matrix M^k will give the number of walks of length k from vertex i to vertex j.

E.g. if, , then .

So, there are 4 different walks of length 3 between the vertices and .

A weighted adjacency table is an adjacency matrix where the value in each cell is the weight of the edge connecting that pair of vertices.

True.

For a directed graph there will be different values in the two cells between specific pairs of vertices in its weighted adjacency table.

For an undirected graph the two cells between each pair of vertices will be the same.

There is no symmetry along the leading diagonal in the weighted adjacency matrix for a directed graph.

A minimum spanning tree is the spanning tree of least weight for a graph.

Kruskal's algorithm and Prim's algorithm are used to minimise the costs, materials or time of a situation that can be modelled by a graph.

This minimisation is done by finding a minimum spanning tree of the graph.

True.

Kruskal's algorithm can only be completed on a complete graph.

False.

The number of edges in a minimum spanning tree will always be one less than the number of vertices in the graph.

A cycle is a walk that starts at a given vertex and ends at the same vertex.

False.

Kruskal's algorithm can only be applied directly to a graph.

Prim's algorithm, however, can be applied directly to a graph or to its adjacency matrix.

The steps involved in Kruskal's algorithm are:

1. Put the edges in ascending order of weight.

2. Select the edge of least weight and add it to the minimum spanning tree.

3. Select the next edge of least weight and add it to the tree (as long as it does not create a cycle with any previously selected edges).

4. Repeat step 3 until all vertices in the graph are connected.

The steps involved in Prim's algorithm on a graph are:

1. Start at any vertex and choose the edge of least weight that is connected to it.

2. 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.

3. Repeat step 2 until all of the vertices are added to the tree.

The steps involved in Prim's algorithm on a matrix are:

1. Select from an vertex, cross out the values in the column associated with that vertex and label the row associated with the vertex, 1

2. Circle the lowest value in any cell along the row, adding the edge to the tree and crossing out the remaining values in its corresponding column.

3. Label the row associated with the same vertex as the column in the previous step, with the next number.

4. Circle the lowest value in any cell along any of the rows that have been labelled and add the edge to your tree, crossing out the remaining values in the column of the circled cell.

5. Repeat STEPS 3 and 4 until all rows have been labelled and all vertices have been added to the tree.

Prim's algorithm is often considered to be more efficient than Kruskal's algorithm, because:

• the edges do not need to be ordered at the start,

• and it is not necessary to check for cycles at every step.

A trail is a walk in which no edge is repeated.

False.

An Eulerian trail is a trail that visits each edge (not vertex) in a graph exactly once.

A circuit is a trail that begins and ends at the same vertex.

An Eulerian circuit is a trail that visits each edge in a graph exactly once and begins and ends at the same vertex.

In an Eulerian graph, the degree of each vertex is even.

A graph that contains an Eulerian trail but not an Eulerian circuit is known as a semi-Eulerian graph.

A semi-Eulerian contains exactly one pair of vertices that have an odd degree.

These odd vertices are the start and finish points of any Eulerian trail.

The Chinese postman problem requires you to find the route of least weight that starts and finishes at the same vertex and traverses every edge in the graph.

True.

If all of the vertices in a graph are even then the shortest route will be the sum of the weights of the edges in an Eulerian circuit.

If a graph contains exactly one pair of odd vertices, then the shortest route between those two vertices will need to be found and repeated on the graph before finding an Eulerian circuit.

If a graph contains 4 odd vertices there will be 6 possible pairings.

E.g. if vertices A, B, C and D are odd, you could have the following pairings:

• AB + CD

• AC + BD

• AD + BC

A path is a walk in which no vertices are repeated.

A Hamiltonian path is a path in which each vertex in a graph is visited exactly once.

A Hamiltonian cycle is a cycle which visits each vertex in a graph exactly once.

A graph is Hamiltonian if it contains a Hamiltonian cycle but only semi-Hamiltonian if it contains a Hamiltonian path but not a Hamiltonian cycle.

False.

There is no algorithm to determine is a graph is Hamiltonian.

The only way to determine if a graph is Hamiltonian is to find a Hamiltonian cycle in it.

The travelling salesman problem requires you to find the route of least weight that starts and finishes at the same vertex and visits every other vertex in the graph exactly once.

In the classical travelling salesman problem, the two conditions that a a graph must meet are:

1. The graph must be complete.

2. The direct route between any two vertices must be the shortest route.

False.

In a graph with 4 vertices, there will be 6 possible Hamiltonian cycles.

Consider a graph with vertices A, B, C and D, the 6 Hamiltonian cycles are:

A B C D A
A B D C A
A C B D A
A C D B A
A D B C A
A D C B A

Unlike the classical travelling salesman problem, the practical travelling salesman problem does not:

• have a complete graph,

• and/or its graph does not meet the triangle inequality (the direct route between two vertices being the shortest route).

The practical travelling salesman problem be converted to the classical travelling salesman problem, by finding the table of least distances.

A table of least distances shows the shortest distance between any two vertices in a graph.

In the travelling salesman problem, the table of least distances be found by completing the following steps:

1. In an empty weighted adjacency table, fill in the information for pairs of vertices that are adjacent in the graph.

   (At this stage check if the direct connections are actually the shortest route and if not, use the alternative shorter route.)

2. Complete the rest of the table by finding the shortest route that can be travelled between each pair of vertices that are not adjacent.

True.

The table of least values has a line of symmetry along the leading diagonal for an undirected graph.

This means that you only need to complete one half carefully first, then you can map over to the second half.

The nearest neighbour algorithm can be used to find the upper bound for the minimum weight Hamiltonian cycle of a graph in the travelling salesman problem.

If there is more than one Hamiltonian cycle that can be found using the nearest neighbour algorithm, the cycle with the smallest value should be chosen as it will give the lowest upper bound.

The steps of the nearest neighbour algorithm are:

1. Choose a starting vertex.

2. 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).

3. Repeat step 2 until all vertices have been visited.

4. Add the final edge to return to the starting vertex.

The deleted vertex algorithm can be used to find the lower bound for the minimum weight Hamiltonian cycle of a graph in the travelling salesman problem.

If there is more than one Hamiltonian cycle that can be found using the deleted vertex algorithm, the cycle with the greatest value should be chosen as it will give the highest lower bound.

The steps of the deleted vertex algorithm are:

• Choose a vertex and delete it along with all edges that are connected to it.

• Find the minimum spanning tree for the remaining graph.

• Add the two shortest edges that were deleted from the original graph to the weight of the minimum spanning tree.

False.

If you have found a cycle the same length as the lower bound then you have found the shortest route for the travelling salesman problem.