How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) – InterviewSolution

InterviewSolution

1.	How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 0(d) 3
Answer» The correct option is (c) 0 The best I can explain: The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting vertices exactly once.

Discussion

No Comment Found

Related InterviewSolutions

What is the minimal Hamming distance between any two correct codewords?(a) 1(b) 2(c) 3(d) 4
What is the message length ‘k’ of a Hamming(7,4) code?(a) 2^r-1(b) 2^r-r+1(c) 2^r-r-1(d) 2^r+1-r
What is the total block length ‘n’ of a Hamming code?(a) 2^r(b) 2^r-1(c) 2^r-1-1(d) 2^r+1
Who invented Hamming codes?(a) Richard Hamming(b) Ross Hamming(c) Shannon(d) Huffman
A two-out-of-five code consists of _________(a) Two 0s and three 1s(b) Three 0s and two 1s(c) Four 0s and one 1s(d) One 0s and four 1s
Halting problem is an example for?(a) decidable problem(b) undecidable problem(c) complete problem(d) trackable problem
________ is the mechanism of sending data bits multiple times to ensure consistency.(a) Repetition(b) Duplication(c) Mirroring(d) Redundancy
To which of the following class does a CNF-satisfiability problem belong?(a) NP class(b) P class(c) NP complete(d) NP hard
How many steps are required to prove that a decision problem is NP complete?(a) 1(b) 2(c) 3(d) 4
Problems that cannot be solved by any algorithm are called?(a) tractable problems(b) intractable problems(c) undecidable problems(d) decidable problems