1.  Connectedness.

(a)  Let G be a connected graph with n vertices. Let v be a vertex of G, and let G/  be the graph

obtained from G by deleting v and all edges incident with v. What is the minimum number of connected components in G/ , and what is the maximum number of connected components in G/ ? For each (minimum and maximum) give an example.

(b)  Find a counterexample with at least 7 nodes to show that the method for finding connected

components of graphs as described in Theorem 26.7 of the coursebook fails at finding strongly connected components of directed graphs. Explain in your own words why your chosen example is a counterexample.

(c)  Prove by induction that for any connected graph G with n vertices and m edges, we have n ≤ m + 1.

(0.5+1+1.5=3 marks)

2.  A graph-theoretic problem.

The computer science department plans to schedule the classes Programming (P), Data Science (D), Artificial Intelligence (A), Machine Learning (M), Complexity (C) and Vision (V) in the following semester. Ten students (see below) have indicated the courses that they plan to take. What is the minimum number of time periods per week that are needed to offer these courses so that every two classes having a student in common are taught at different times during a day. Two classes having no student in common can be taught at the same time. For simplicity, you may assume that each course consists of a single 50 min lecture per week.

Anden: A, D           Brynn: V, A, C     Chase: V, C, A    Denise: C, A, M Everett: M, A, D    Francoise: C, M    Greg: P, V, A      Harper: A, P, D Irene: M, D, A        Jenny: P, D

To get full marks, your answer to this question should be clear and detailed. In particular, you are asked to explain which graph-theoretic concept can be used to model the above situation, apply this concept to the situation, and explain how the resulting graph can be exploited to answer the question.

(3 marks)

3.  Graph algorithms.

Consider a directed graph G as defined in Definition 20.1 of the coursebook. Recall that directed graphs do not have loops or multiple arcs between any two nodes. Run DFS on G. Let F be the number of forward arcs in the resulting search forest, and let C be the number of cross arcs in the resulting search forest. As in class, for DFS, we follow the rule that, whenever there are multiple nodes to choose from, we choose the one with the smallest label.

Write an algorithm that returns, for each input graph G, the sum F + C .

(4 marks, 1 mark for each test case)

Input format. The input consists of a sequence of one or more directed graphs. Each directed graph G is represented by an adjacency list. The first line is an integer n that indicates the order of G. This is followed by n white space separated lists of adjacencies for nodes labeled 0 to n - 1. The input is terminated by a line consisting of a single zero. This line should not be processed. An example input that contains two directed graphs is shown next. Note that the directed graph on the right, consists of two connected components.

6

1  2  3

2

3  5

4

5

6

3  5

2

4

4

0

0                                  1

3                                 2