Random graph walk. A graph $($V $,$ E $)$ consists of a set V of vertices and

a relation E : V $$ V determining adjacency of pairs of vertices. In this

question we consider the $($undirected$)$ graph

V :$=$range$(5)$

E :$=\{(0,2),(2,0),(0,3),(3,0),(0,4),(4,0),$

$(1,3),(3,1),(1,2),(2,1),(3,2),(2,3)\}$

and simulate a robot$$s walk around it$,$ moving between adjacent vertices.

The robot starts at vertex $0$ and, from each vertex v where it finds itself,

chooses its next vertex randomly $($uniformly$)$ from the neighbours of v$.$

$($a$)$ Draw the graph $($V $,$ E $).$

$($b$)$ Recall from class how to convert the relation E : V $$ V to a function

from V to the set of subsets of V $.$ Write down that function for $($V

$,$ E $)$ and express the graph as a Python dictionary.

$($c$)$ Give an algorithm in design space for the robot$$s progress, with a

variable v : V for its current position and a list h keeping a history

of vertices visited. Your algorithm should use a natural number N

representing the number of steps the robots takes.

$($d$)$ Now implement and test your algorithm.

$($e$)$ We$$re interested to know whether or not the robot spends about the

same amount of time at each vertex. So instead of returning the

history h we want to return the frequency of each vertex in h$.$ Even

better would be to print the vertices in order of frequency, or even

graph the output.

Return to design space and modify your algorithm to yield the fre

quency of each vertex. This demonstrates an importance use of de

sign space: modifying an algorithm. Decide how you want to display

the result. Now downcode the new algorithm and test it$.$

$($f$)$ The degree of a vertex is the number of its neighbours. What are the

degrees of the vertices? Make a conjecture about which vertices the

robot visits least often.