Week 07 Tutorial Answers
Graphs
Graph Representations
-
Consider the following graph
The edges are labelled simply for convenience in describing graph properties.
- How many edges does it have?
- How many cycles are there in the graph?
- How many cliques are there in the graph?
- What is the degree of each vertex?
-
How many edges in the longest path from 5 to 8?
(without traversing any edge more than once)
Answer:
- 11 edges (labelled a..k)
- 6 cyles: 0-1-7-8-0, 1-2-7-1, 2-3-7-2, 0-1-2-7-8-0, 0-1-2-3-7-8-0, 1-2-3-7-1
- 2 cliques: {1, 2, 7}, {2, 3, 7} (clique = complete subgraph with at least 3 nodes)
- d(0) = 2, d(1) = 3, d(2) = 3, d(3) = 3, d(4) = 2, d(5) = 1, d(6) = 1, d(7) = 5, d(8) = 2
- 7 edges, path is 5-4-3-2-7-1-0-8 or 5-4-3-7-2-1-0-8
-
How is the adjacency matrix for a directed graph different to that for an undirected graph?
Answer:
The adjacency matrix for an undirected graph is symmetric and has zeroes on the leading diagonal (no self-edges). The adjacency matrix for a directed graph is typically not symmetric and can have non-zero values on the leading diagonal (self-edges are allowed).
-
Consider the following map of streets in the Sydney CBD:
Represent this as a directed graph, where intersections are vertices and the connecting streets are edges. Ensure that the directions on the edges correctly reflect any one-way streets (this is a driving map, not a walking map). You only need to make a graph which includes the intersections marked with red letters. Some things that don't show on the map: Castlereagh St is one-way heading south and Hunter St is one-way heading west.
For each of the following pairs of intersections, indicate whether there is a path from the first to the second. If there is a path, enumerate it as a set of vertices. If there is more than one path, show two different paths.
from intersection \( D \) on Margaret St to intersection \( L \) on Pitt St
from intersection \( J \) to the corner of Margaret St and York St (intersection \( A \))
from the intersection of Margaret St and York St (\( A \)) to the intersection of Hunter St and Castlereagh St (\( M \))
from intersection \( M \) on Castlereagh St to intersection \( H \) on York St
Answer:
The graph is as follows. Bi-directional edges have two-way arrows, rather than having two separate edges going in opposite directions.
For the paths:
\( D \to E \to G \to L \) and there are no other choices that don't involve loops through \( D \)
\( J \to I \to B \to A \) or \( J \to K \to F \to D \to C \to B \to A \)
You can't reach \( M \) (or \( N \) or \( P \)) from \( A \) on this graph. Real life is different, of course.
\( M \to G \to F \to D \to C \to B \to A \to H \) or \( M \to G \to F \to K \to J \to I \to H \)
Graph Traversal
-
Show what would be printed by the iterative breadth-first and depth-first traversals in the functions below on the following graph.
When choosing which neighbour to visit next, always choose the smallest unvisited neighbour. At each step, show the state of the
Queue(BFS) or theStack(DFS).void breadthFirst(Graph g, Vertex src) { int *visited = calloc(g->nV, sizeof(int)); Queue q = QueueNew(); QueueEnqueue(q, src); while (!QueueIsEmpty(q)) { Vertex v = QueueDequeue(q); if (visited[v]) { continue; } visited[v] = 1; printf("%d\n", v); for (Vertex w = 0; w < g->nV; w++) { if (g->edges[v][w] && !visited[w]) { QueueEnqueue(q, w); } } } QueueFree(q); free(visited); }
void depthFirst(Graph g, Vertex src) { int *visited = calloc(g->nV, sizeof(int)); Stack s = StackNew(); StackPush(s, src); while (!StackIsEmpty(s)) { Vertex v = StackPop(s); if (visited[v]) { continue; } visited[v] = 1; printf("%d\n", v); for (Vertex w = g->nV - 1; w >= 0; w--) { if (g->edges[v][w] && !visited[w]) { StackPush(s, w); } } } StackFree(s); free(visited); }
Show the results for each of the following function calls:
breadthFirst(g, 0); breadthFirst(g, 3); depthFirst(g, 0); depthFirst(g, 3);
Answer:
For
breadthFirst(g, 0):# Printed Visited Queue (front at left) 0 - - 0 1 0 0 1 2 5 6 7 2 1 0 1 2 5 6 7 7 3 2 0 1 2 5 6 7 7 4 5 0 1 2 5 6 7 7 3 4 5 6 0 1 2 5 6 7 7 3 4 4 7 6 7 0 1 2 5 6 7 7 3 4 4 7 4 7 3 0 1 2 5 6 7 3 4 4 7 4 4 8 4 0 1 2 5 6 7 3 4 4 7 4 4
For
breadthFirst(g, 3):# Printed Visited Queue (front at left) 0 - - 3 1 3 3 4 5 2 4 3 4 5 6 7 3 5 3 4 5 6 7 0 4 6 3 4 5 6 7 0 0 7 5 7 3 4 5 6 7 0 0 7 0 1 6 0 3 4 5 6 7 0 0 7 0 1 1 2 7 1 3 4 5 6 7 0 1 1 2 8 2 3 4 5 6 7 0 1 2 -
For
depthFirst(g, 0):# Printed Visited Stack (top at left) 0 - - 0 1 0 0 1 2 5 6 7 2 1 0 1 7 2 5 6 7 3 7 0 1 7 4 6 2 5 6 7 4 4 0 1 7 4 3 5 6 6 2 5 6 7 5 3 0 1 7 4 3 5 5 6 6 2 5 6 7 6 5 0 1 7 4 3 5 5 6 6 2 5 6 7 7 6 0 1 7 4 3 5 6 6 2 5 6 7 8 2 0 1 7 4 3 5 6 2 5 6 7
For
depthFirst(g, 3):# Printed Visited Stack (top at left) 0 - - 3 1 3 3 4 5 2 4 3 4 5 6 7 5 3 5 3 4 5 0 6 7 5 4 0 3 4 5 0 1 2 6 7 6 7 5 5 1 3 4 5 0 1 7 2 6 7 6 7 5 6 7 3 4 5 0 1 7 6 2 6 7 6 7 5 7 6 3 4 5 0 1 7 6 2 6 7 6 7 5 8 2 3 4 5 0 1 7 6 2 6 7 6 7 5
Miscellaneous Graph Theory
-
What is the difference between a connected graph and a complete graph? Give simple examples of each.
Answer:
A connected graph is a graph where all vertices are reachable from all others, while a complete graph is a graph where all vertices are directly connected (by edges) to all others.
Connected graphs have the property that there is a single connected component. Complete graphs have the property that every vertex has \( V - 1 \) incident edges, where \( V \) is the number of vertices in the graph. A graph cannot be complete if it is not connected. Some simple examples:
Graphs 1, 2 and 3 are connected. Graph 2 is also complete. Graph 4 is not connected, and therefore also not complete despite each of the individual components being complete.
-
Consider the following graph with multiple connected components:
And a vertex-indexed connected components array that might form part of the
Graphrepresentation structure for this graph:cc[] = {0, 0, 0, 1, 1, 1, 0, 0, 0, 1}Identify any bridges in the graph (note: a bridge is an edge that, if removed, would cause the number of connected components to increase)
Show how the
cc[]array would change if edge \( d \) was removedShow how the
cc[]array would change if edge \( b \) was removed
Answer:
Edges \( b, e, f, g, h, i \) are all bridges; removing any one of them would cause the number of connected components to increase
After removing \( d \),
cc[] = {0, 0, 0, 1, 1, 1, 0, 0, 0, 1}(i.e., unchanged)After removing \( b \),
cc[] = {0, 0, 2, 1, 1, 1, 2, 0, 2, 1}
-
What is the difference between an Euler path/tour and a Hamilton path/tour? Identify any Euler/Hamilton paths/tours in the following graphs:
Answer:
An Euler path is a path that traverses each edge in the graph exactly once. An Euler tour is an Euler path that ends at the same vertex where it started. A Hamilton path visits each vertex in the graph exactly once. A Hamilton tour is a Hamilton path that ends at the same vertex where it started (which means that the starting vertex appears in the path twice).
Graph 1 has both Euler and Hamilton paths (e.g. \( [0, 1, 2] \), but cannot have tours as there are no cycles.
Graph 2 has both Euler and Hamilton paths (e.g. \( [0, 1, 2] \)), and also has both Euler and Hamilton tours (e.g. \( [0, 1, 2, 0] \)).
Graph 3 has neither Euler nor Hamilton paths, nor Euler nor Hamilton tours.
Graph 4 has Hamilton paths (e.g. \( [0, 1, 2, 3] \)) and a Hamilton tour (e.g. \( [0, 1, 2, 3, 0] \)), but it has neither an Euler path nor an Euler tour.
-
Write a function to check whether a path, supplied as an array of
Edges is an Euler path. Assume the function has interface:bool isEulerPath(Graph g, Edge e[], int nE)
where
e[]is an array ofnEedges, in path order.Answer:
// check whether a given path is a Euler path bool isEulerPath(Graph g, Edge e[], int nE) { assert(g != NULL); // includes all edges if (g->nE != nE) { return false; } // edges are actually in the graph for (int i = 0; i < nE; i++) { if (g->edges[e[i].v][e[i].w] == 0) { return false; } } // is actually a path for (int i = 0; i < nE - 1; i++) { if (e[i].w != e[i + 1].v) { return false; } } // includes edges exactly once for (int i = 0; i < nE; i++) { for (int j = i + 1; j < nE; j++) { if (e[i].v == e[j].v && e[i].w == e[j].w) return false; if (e[i].v == e[j].w && e[i].w == e[j].v) return false; } } return true; }
-
Find a Hamilton path and a Hamilton tour (if they exist) in the following graph:
If there is no Hamilton path or tour for the above graph, modify the edges so that such a path/tour exists.
Answer:
Hamilton paths: There are many - for example, 1-0-3-2-6-5-4, 4-0-1-5-6-2-3, etc.
Hamilton tour: There are no Hamilton tours in the original graph. There are various ways to create a Hamilton tour by adding a single edge - for example, if we added an edge between 3 and 4, a Hamilton tour would be 0-1-5-6-2-3-4-0.
The following graph has two edges from each vertex and has Hamiton tours: 4-0-1-5-6-2-3-4 or 6-2-3-4-5-1-0-6 or 6-5-1-0-4-3-2-6 or ...
