CS 163/265, Winter 2024, Practice Problem Set 1

1. Consider the directed graph \(G\) defined by the Python dictionary {a: [b, c], b: [c], c: [a]}. Compute the lazy web surfer probabilities \(P_i[x]\) for each vertex and for \(i=1, 2, 3\). (You may find it easier to write a program to do this.)

2. 1. Write the Python representation for the graph obtained from \(G\) by reversing the direction of each of its edges.

   2. Write pseudocode (or Python code) for an algorithm that reverses all the edges of a graph given in the Python representation.

3. For the graph \(G\) from question 1, there are six permutations of the three vertices. Which of these could be the result of a breadth first search? (You should not assume that the line "for each edge in G from v to w" in the breadth first search pseudocode will always list these edges in the same order as given in the Python representation; any order is possible.) Draw a BFS tree for each of these orders.

4. The lecture notes define strong connectivity using an equivalence relation on the vertices of a directed graph.

   1. Suppose we instead define a relation on the edges of a directed graph, in which we say that two edges are "tourmates" if they are both part of a tour (that is, a closed trail, or a cycle allowing repeated vertices or edges). For two edges \(e\) and \(f\) that both belong to the same strongly connected component of a graph, explain how to find a closed trail that includes both of them, showing that they are tourmates. (Hint: Apply the definition of the strong connectivity relation to the endpoints of \(e\) and \(f\).)

   2. Use an example to explain why being tourmates is not an equivalence relation.