Question

I need help for Q11

Please if you can, answer this question too. I need B

Q11. A complete graph is a graph where all vertices are connected to all other vertices. A Hamiltonian path is a simple path that contains all vertices in the graph. Show that any complete graph with 3 or more vertices has a Hamiltonian path. How many Hamiltonian paths does a complete graph with n vertices has? Justify your answer Q1. Draw thee 13-entry hash table that results from using the hash function h(k) = (3k - 5) mod 13 to hash the keys 31, 45, 14, 89, 24, 95, 12, 38, 27, 16, and 25, assuming that collisions are handled in the following ways: a) inear probing b) double hashing using the secondary hash function h'(k) = 7- (kmod 7).

Answer 1

11) According to Dirac's theorem a simple graph with 3(n>=3) or more vertices is Hamiltonian, if every vertex on the graph has a degree >= n/2.

Now in a complete graph with n vertices, the degree of each vertex is (n-1).

For n>=3 (n-1) will be always greater than n/2.

Hence the theorem holds and any complete graph with n>=3 contains a Hamiltonian path.

The number of Hamiltonian paths in a complete graph with n vertice is n! because, every vertex of the complete graph can be a starting point of the path and can reach every other vertex.

1) b) 31:

h(31) = (31*3 - 5)mod13 = (93-5)mod13 = 88mod13 = 10

13 will be mapped to 10.

45:

h(45) = (45*3 - 5)mod13 = (135-5)mod13 = 130mod13 = 0

45 will be mapped to 0.

14:

h(14) = (14*3 - 5)mod13 = (42-5)mod13 = 37mod13 = 11

14 will be mapped to 11.

89:

h(89) = (89*3 - 5)mod13 = (267-5)mod13 = 262mod13 = 2

89 will be mapped to 2.

24:

h(24) = (24*3 - 5)mod13 = (72-5)mod13 = 67mod13 = 2

As there is a collision we will do double hashing.

(h(24) + 1*h'(24))mod13 = (2 + (7 - (24mod7)))mod13 = (2 + 7 - 3)mod13 = 6mod13=6

So, 24 will be mapped to 6.

95:

h(95) = (95*3 - 5)mod13 = (285-5)mod13 = 280mod13 = 7

95 will be mapped to 7.

12:

h(12) = (12*3 - 5)mod13 = (36-5)mod13 = 31mod13 = 5

12 will be mapped to 5.

38:

h(38) = (38*3 - 5)mod13 = (114-5)mod13 = 109mod13 = 5

As there is a collision we will do double hashing.

(h(38) + 1*h'(38))mod13 = (5 + (7 - (38mod7)))mod13 = (5 + 7 - 3)mod13 = 9mod13=9

So, 38 will be mapped to 9.

27:

h(27) = (27*3 - 5)mod13 = (81-5)mod13 = 76mod13 = 11

As there is a collision we will do double hashing.

(h(27) + 1*h'(27))mod13 = (11 + (7 - (27mod7)))mod13 = (11 + 7 - 6)mod13 = 12mod13=12

So, 27 will be mapped to 12.

27:

h(27) = (27*3 - 5)mod13 = (81-5)mod13 = 76mod13 = 11

As there is a collision we will do double hashing.

(h(27) + 1*h'(27))mod13 = (11 + (7 - (27mod7)))mod13 = (11 + 7 - 6)mod13 = 12mod13=12

So, 27 will be mapped to 12.

16:

h(16) = (16*3 - 5)mod13 = (48-5)mod13 = 43mod13 = 4

So, 16 will be mapped to 4.

25:

h(25) = (25*3 - 5)mod13 = (75-5)mod13 = 70mod13 = 5

As there is a collision we will do double hashing.

(h(25) + 1*h'(25))mod13 = (5 + (7 - (25mod7)))mod13 = (11 + 7 - 3)mod13 = 15mod13=2

As there is again collision so we go for second round of double hashing.

(h(25) + 2*h'(25))mod13 = (5 + 2*(7 - (25mod7)))mod13 = (11 + 2*(7 - 3))mod13 = 19mod13=6.

As there is again collision so we go for third round of double hashing.

(h(25) + 3*h'(25))mod13 = (5 + 3*(7 - (25mod7)))mod13 = (11 + 3*(7 - 3))mod13 = 23mod13=10.

As there is again collision so we go for fourth round of double hashing.

(h(25) + 4*h'(25))mod13 = (5 + 4*(7 - (25mod7)))mod13 = (11 + 4*(7 - 3))mod13 = 27mod13=1.

Finally, 25 will be mapped to 1.

45
25
89
16
12
24
95
38
31
14
27