1.

In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be ______(a) 728(b) 450(c) 360(d) 260I had been asked this question in a national level competition.My query is from Graphs Properties in chapter Graphs of Discrete Mathematics

Answer»

Right option is (c) 360

The explanation is: A HAMILTONIAN CYCLE in a CONNECTED graph G is defined as a closed path that traverses every vertex of G exactly once EXCEPT the STARTING vertex, at which the path also terminates. In an n-complete graph, there are (n-1)!/2 hamiltonian cycles and so the answer is 360.


Discussion

No Comment Found

Related InterviewSolutions