Week 07 Tutorial Questions

Graphs

Graph Representations

Consider the following graph

The edges are labelled simply for convenience in describing graph properties.
1. How many edges does it have?
2. How many cycles are there in the graph?
3. How many cliques are there in the graph?
4. What is the degree of each vertex?
5. How many edges in the longest path from 5 to 8?
  (without traversing any edge more than once)
How is the adjacency matrix for a directed graph different to that for an undirected graph?
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.
1. from intersection \( D \) on Margaret St to intersection \( L \) on Pitt St
2. from intersection \( J \) to the corner of Margaret St and York St (intersection \( A \))
3. from the intersection of Margaret St and York St (\( A \)) to the intersection of Hunter St and Castlereagh St (\( M \))
4. from intersection \( M \) on Castlereagh St to intersection \( H \) on York St

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 the Stack (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);

Miscellaneous Graph Theory

What is the difference between a connected graph and a complete graph? Give simple examples of each.
Consider the following graph with multiple connected components:

And a vertex-indexed connected components array that might form part of the Graph representation structure for this graph:
```
cc[] = {0, 0, 0, 1, 1, 1, 0, 0, 0, 1}
```
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)
2. Show how the cc[] array would change if edge \( d \) was removed
3. Show how the cc[] array would change if edge \( b \) was removed
What is the difference between an Euler path/tour and a Hamilton path/tour? Identify any Euler/Hamilton paths/tours in the following graphs:
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 of nE edges, in path order.
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.