Chapter 12 - Graphs and Networks 1

Question 1

Define a Graph, Vertex, Face and Edge.

Answer 1

• A Graph is a diagram involving a set of points and interconnecting lines.
• A Vertex is a point on a Graph.
• An Edge is a line joining two points.
• A Face is a region within the edges of a graph, including the singular region outside of it.

Question 2

Define a complete graph?

Answer 2

A complete graph is a graph that has an edge connecting all possible pairs of vertices. The notation is Kₙ.

Question 3

Define a complete bipartite graph?

Answer 3

A complete bipartite graph connects m vertices to n vertices. The notation is Kₙٖₘ

Question 4

Define a degree in graph theory, and what is the relationship between the degrees and edges?

Answer 4

A degree in graph theory is defined as the number of connections each edge has. The total number of degrees is equal to 2 times the number of edges.

Question 5

Define a Planar Graph.

Answer 5

A planar graph is a graph that can be embedded in the plane, in such a way that its edges only intersect at their endpoints. (no intersecting edges.)

Question 6

What is Euler’s Formula for Planar Graphs?

Answer 6

Euler’s Formula, applicable for finite, connected, planar graphs:

v + f - e = 2.

Vertices + Faces - Edges (including infinite outside face) = 2

Question 7

What are the two relationships connecting edges and graphs?

Answer 7

For a simple, connected, planar graph:

e ≤3v - 6 AND At least three edges, and every edge touches at most two faces.

2e ≥ 3f AND More than one edge.

Question 8

State the triangle inequality.

Answer 8

The triangle inequality in Graph Theory:

AB + BC ≥ AC, where AC is the hypotenuse.

Question 9

What is a walk traversal?

Answer 9

A walk traversal is a continuous journey across a graph with no restrictions on repeating edges or vertices.

Question 10

What is a trail traversal? Therefore, what is a closed trail?

Answer 10

A trail traversal is a continuous journey across a graph that has no repeated edges. If it returns to the starting vertex, it is a closed trail.

Question 11

What is a path traversal? Therefore, what is a cycle?

Answer 11

A path traversal is a continuous journey across a graph which has no repeated edges OR vertices. If you return to the start vertex, this is called a cycle.

Question 12

What is a Hamiltonian Cycle?

Answer 12

A cycle which visits every vertex once and only once is called a Hamiltonian Cycle.

Question 13

State the steps of Kruskal’s Algorithm.

Answer 13

Kruskal’s Algorithm:

Step 1: Choose the arc with minimum weight.
Step 2: Choose the arc with the least weight from the remaining arcs, avoiding those already chosen.
Step 3: If any nodes remain unconnected, go to Step 2.

Question 14

State the steps of Prim’s Algorithm (on a graph).

Answer 14

Prim’s Algorithm:

Step 1: Choose any node to be the first the connected set.
Step 2: Choose the arc of minimum weight joining a connected node to an unconnected node. Add this arc to the spanning tree and the node to the connected set.
Step 3: If any unconnected nodes remain, go to Step 2.

Question 15

State the steps of Prim’s Algorithm (on a graph).

Answer 15

Prim’s Algorithm (on a matrix):

Step 1: Select the first node.
Step 2: Cross out the row and number the column for the chosen node.
Step 3: Find the minimum undeleted weight in the numbered columns. Circle this value. The node for this row is the next chosen node.
Step 4: Repeat steps 2 and 3 until all nodes have been chosen.

Question 16

State the steps for the Route Inspection Algorithm.

Answer 16

Route Inspection Algorithm:

Step 1: Identify all the odd nodes.
Step 2: List all the possible pairings of the odd nodes.
Step 3: For each pairing find the shortest routes between paired nodes and the total weight of those routes.
Step 4: Choose the pairing with the smallest total.
Step 5: Repeat the shortest route arcs (equivalent to adding extra arcs to the network). The network is now traversable.

Question 17

Name the characteristic of the Route Inspection Algorithm to do with the frequency it passes through a node.

Answer 17

The inspection route passes 1/2n times through a node of degree n.

Question 18

Define the travelling salesman problem.

Answer 18

The travelling salesman problem tries to find a route that visits every node of a network and returns to the start in the shortest possible distance.

Question 19

How do you solve a travelling salesman problem?

Answer 19

To a solve a practical travelling salesman problem with n nodes:

• Create a complete network, Kₙ, of shortest distances between pairs of nodes.
• Find a minimum weight Hamiltonian cycle for the complete network (this is the classical problem).
• Interpret the solution in the practical situation.

Question 20

Describe the relationship between nodes and possible tours. (TSP)

Answer 20

A network with n nodes has 1/2(n-1)! possible tours.

Question 21

State the steps for the nearest neighbour algorithm. (TSP)

Answer 21

The nearest neighbour algorithm:

Step 1: Choose a starting node, V.
Step 2: From your current position, choose the arc with minimum weight leading to an unvisited node. Travel to that node.
Step 3: If there are unvisited nodes, go to Step 2.
Step 4: Travel back to V.

Question 22

Describe how you determine whether a solution, T, is optimal? (TSP)

Answer 22

For a solution T, to determine an optimal value, you find two values:

Lower Bound ≤T≤Upper Bound.

Question 23

What is true for any tour? (TSP)

Answer 23

The length of any known tour is an upper bound for a solution.

Question 24

Describe the relationship between minimum spanning trees and upper bounds for a solution. (TSP)

Answer 24

(2 x length of the minimum spanning tree) is an upper bound.

Question 25

How do you find a lower bound for a TSP?

Answer 25

To find a lower bound:

Step 1: Choose a node V.
Step 2: Identify the two lowest weights, p and q, of the arcs connected to V.
Step 3: Remove V and its connecting arcs from the network. Find the total weight, m, of the minimum spanning tree of the remaining subgraph.
Step 4: Calculate lower bound = p + q + m.
Step 5: If possible, choose another node V and go to Step 2.
Step 6: Choose the largest result obtained as the best lower bound.
Step 7: If you find a lower bound which forms a tour, then that tour is the optimal solution. If none of the possible lower bounds form a tour, the optimal tour must be greater than the best lower bound.

Question 26

Define the feasibility condition.

Answer 26

The feasibility condition states that the flow in an arc cannot be greater than its capacity.

Question 27

Define the conservation condition.

Answer 27

The conservation condition states that, at every node apart from S source and T sink, total inflow = total outflow.

And:

Total outflow from S source = total inflow to T sink.

Question 28

What is the capacity of a cut, in network flows?

Answer 28

The capacity of a cut is the sum of the capacities of those arcs of the cut which are directed from X to Y.

You describe a cut either by listing the set of arcs in the cut (the cut set) or by listing the nodes in the source set X, and the sink set Y.

Question 29

What is the value of the flow in a cut, in network flows?

Answer 29

The value of any flow is less than or equal to the capacity of any cut.

Question 30

State the maximum flow-minimum cut theorem.

Answer 30

The maximum. flow-minimum cut theorem states that the value of the maximal flow is equal to the capacity of a minimum cut.