T Naughton, NUIM
Back to CS403/SE307/CS355 home

Lab 5 - Graphs

First, make sure you are assigned to a team by a demonstrator and go to the space allocated for your team. The object of this lab is to work in teams to answer the problems below. Each team will hand up its solutions at the end of the lab.

Graphs

A graph is a collection of vertices (nodes) and edges. Consider the following graph G₀.

Each edge joins two nodes together. Some pairs of nodes might not have an edge joining them. For G₀, we could say that the graph contains the set V of nodes where V = {0, 1, 2, 3}. We could also describe the collection of edges as a set. This set E is the set of all pairs (x, y) where both x and y are elements of V, x y (there is no edge from a node to itself), and where x and y are joined by an edge. So for G₀, E would be E = {(0,1), (1,2), (0,2), (0,3)}. Because E is a set, it doesn't matter in what order we write the elements of E. It also doesn't matter what order x and y are in each edge (x, y); the edge (0, 1) is the same as the edge (1, 0). To completely describe G₀ we need to specify both its vertices and edges. So we would say that the graph G₀ is defined as G₀ = (V, E) where V and E are defined above.

A directed graph has arrows on its edges. Here the order of x and y in each edge (x, y) is important. The edge (x, y) means there is an edge from x to y but says nothing about whether there is an edge from y to x. The directed graph G₁ is given below.

In G = (V, E) notation, G₁ is defined as G₁ = ({0, 1, 2, 3, 4, 5}, {(0,1), (3,2), (2,4), (4,3), (4,5), (5,4)}).

Problem 1. Express the following directed graph in G₂ = (V, E) notation.

Problem 2. Illustrate what the directed graph G₃ = ({0, 1, 2}, {(0,2), (1,2), (2,1)}) would look like in diagram form.

A path in a graph is a sequence of nodes connected by edges. In G₁ above, we can see that there is a path from 0 to 1, and from 2 to 5, but there is no path from 0 to 3 or from 1 to 0. The path from 5 to 2 would be specified by the sequence of nodes (5, 4, 3, 2) that show you the route you could take from 5 to 2. Without looking at the diagram form of G₁, we can tell there is a path from 5 to 2 because the edges (5,4), (4,3), and (3,2) are present in the set E of G₁.

The path language is defined as PATH = {< G, s, t > : G is a directed graph that has a path from s to t}. So, < G₁, 5, 2 > would be in PATH and < G₁, 0, 1 > would be in PATH but < G₁, 1, 0 > would not be in PATH.

Problem 3. (i) Is < G₂, 2, 3 > in PATH? If so, specify the path as a sequence of nodes.
(ii) Is < G₂, 0, 2 > in PATH? If so, specify the path as a sequence of nodes.

Problem 4. (i) What is the maximum number of edges in a directed graph with 2 nodes?
(ii) With 3 nodes?
(iii) With 4 nodes?
(iv) With 5 nodes? (At this point, you might be quicker working out the equation that describes the relationship between number of nodes in a directed graph and maximum number of edges.)
(v) With 6 nodes?
(vi) With 7 nodes?

Problem 5. (i) For this question, consider only directed graphs with a maximum number of edges (i.e. an edge between every two nodes, in both directions). We call these fully-connected graphs. A path that goes through every node exactly once in a graph with m nodes is a path of length m (it has m-1 edges). What is the maximum number of different paths that go though every node exactly once in a fully-connected directed graph with 2 nodes?
(ii) With 3 nodes?
(iii) With 4 nodes?
(iv) With 5 nodes? (At this point, you might be quicker working out the equation that describes the relationship between number of nodes in a directed graph and number of different paths that go through every node exactly once.)
(v) With 6 nodes?
(vi) With 7 nodes?