A vertex listing of a graph G(V, E) is an ordering of the vertices such that con
ID: 3724988 • Letter: A
Question
A vertex listing of a graph G(V, E) is an ordering of the vertices such that consecutive vertices in the ordering are adjacent in the graph. Let’s consider a Qn Vertex Listing: this is a vertex listing of the vertices of Qn starting from the vertex labeled with all 0 bits such that no vertex is repeated and all vertices are included in the listing exactly once. For example, the Q1 vertex listing is 0, 1. A Q2 vertex listing is 00, 01, 11, 10. A Q3 vertexlistingis000,001,011,010,110,111,101,100.
(c) Provide a recursive algorithm to produce a Qn Vertex Listing. (there must be at least one recursive call for any case that is not a base case.)
(d) Prove the correctness of your recursive algorithm Qn Vertex Listing.
Explanation / Answer
c) Let us look at the sequence of the subsequent vertex listing
for v=1 : 0 1
for v=2 : 00 01 11 10
for v=3 : 000 001 011 010 110 111 101 100
Observe first half of the vertex listing of any vertex after 1st vertex , it is nothing but 0 appended before the vertex listing of previous vertex.
Now observe the second half of the vertex listing of any vertex after 1st vertex, It is nothing but 1 appended before the vertex listing of previous vertex taken in opposite order.
For example, vertex listing of v=2 is 00 01 11 10
first half : 00 01, vertex listing of previous vertex: 0 1
We can observe the 00 01 is obtained by appending 0 before 0 1.
Now look at second half: 11 10, vertex listing of previous vertex : 0 1, reverse : 1 0
We can see that 11 10 is obtained by appending 1 before 1 0.
Now let us write the algorithm, it will take integer n as input and return list:
-------------------------------------------------------------------------------------------
QnVertexListing( int n) :
if n=1
List=[0 1]
return List
else
List = [];
Plist = QnVertexListing(n-1);
for each element E in Plist
append 0 before E
add it to List
end
Reverse PList
for each element E in Plist
append 1 before E
add it to List
end
return List
end
--------------------------------------------------------------------------------------------
D) Now we have to prove the correctness of the algorithm.
Vertex listing of any vertex follows the following rule:
In the vertex listing of any vertex, consecutive elements in the list differ by a single bit
(you can verify it in the list above, it is actually how the vertex listing is created.)
We can prove the correctness of our algorithm by induction:
First step:
For v=1: vertex listing 0 1
every element differ only by single bit, correct for v=1
Second Step:
Assume that our algorithm gives correct answer for v=k
So, list returned for k vertex is correct i.e every element of this list differs only by a single bit.
Final step/Induction step:
Now we have to prove that our algorithm gives correct list for v=k+1 also.
To calculate the vertex listing for v=k+1, first half of list we are creating by appending 0 before the vertex listing of v=k, Since elements of vertex listing of v=k differ only by 1 bit and we are appending same bit before every element, resulting list will also differ by only 1 bit. hence first half of the list is correct.
Now for second half, we are reversing the list. When reversing the list, elements will still differ by 1 bit. and appending same bit before every element will give us a list that will differ by 1 bit.
Now we ave to check wether last element of first half and first element of second follow this rule.
Last element of first half is created by appending 0 before last element of vertex listing v=k and fisrt element of second half is created by appending 1 before the same element. Appendin 0 and 1 before last element of list of v=k give s us element that will differ by only 1 bit.
Hence, vertex listing returned by our algorithm for v=k+1 is correct.
Hence by principle of mathematical induction, our algorithm is correct.