Question
Please Assist witn #15.
For the undirected graph Below, find and solve a recurrence
relation for the number of closed v-v walks of length
n %u2265 1, if we allow such a walk, in this case, to contain or consist
of one or more loops.
5e Ch11.pdf (SECURED) Adobe Read File Edit View Window Help Tools Sign Comment 70 200% Sig EKT Highlight Existing Field Please fill out the following form. You can save data typed into this form Export P Create PDF Adobe CreatePDF W4 the wheel with four spokes. The wheel W5 with five represe convert files to PDF and easily combine them with other file types with a paid spokes appears in Fig. 11.11 (c). Determine how many cy figure subscription ct Fi PDF: cles of length 4 there are in each of these graphs unit int edge is b) In general, if n E Z+ and n 3, then the wheel with n Select File spokes is the graph made up of a cycle of length n together respon with an additional vertex that is adjacent to the n vertices in part Send Files spond Store Files of the cycle. The graph is denoted by Wn. (i) How many interva cycles of length 4 are there in Wn ii) How many cycles in sists of Wn have length n to the g 15. For the undirected graph in Fig. 11.12, find and solve a re part (c currence relation for the number of closed v-v walks of length interva n 1, if we allow such a walk, in this case, to contain or consist nary se of one or more loops of the with th thr Figure 11.12 qu 16. Unit-Interval Graphs. For n z 1, we start with n closed in- tervals of unit length and draw the corresponding unit-interval int graph on n vertices, as shown in Fig. 11.13. In part (a) of the figure we have one unit interval. This corresponds to the single 8.50 x 11.00 in
Explanation / Answer
Let V(n) be the number of walks of length n that start and end at V, and let W(n) be the number of walks of length n that start and end at W. Then V(n+1) = V(n) + W(n), since the previous vertex had to be either V or W. However, W can only be reached from V, so W(n+1) = V(n). The base cases are V(1) = 1, since there's only one way to start and end at V after one move, and W(1) = 1, since there's only one way to start at V and end at W after one move.
So now we've got V(n+1) = V(n) + W(n) = V(n) + V(n-1). This looks very similar to the Fibonacci Sequence. And in fact, V(1) = 1, V(2) = 2, V(3) = 3, V(4) = 5, etc. So in general, V(n) is the (n+1)th Fibonacci number.