Consider a simple, complete graph with n nodes. Testing for a Hamiltonian circuit by

Chapter 7, Problem 31

(choose chapter or problem)

Consider a simple, complete graph with n nodes. Testing for a Hamiltonian circuit by trial and error could be done by selecting a fixed starting node and then generating all possible paths from that node of length n. a. How many paths of length n are there if repetition of arcs and nodes is allowed? b. How many paths of length n are there if repetition of arcs and nodes is allowed but an arc may not be used twice in succession? c. How many paths of length n are there if nodes and arcs cannot be repeated except for the starting node? (These are the Hamiltonian circuits.) d. To solve the traveling salesman problem in a weighted graph, assume a fixed starting point at node 1 and generate all possible Hamiltonian circuits of length n to find one with minimum weight. If it takes 0.000001 seconds to generate a single Hamiltonian circuit, how long will this process take in a simple, complete graph with 15 nodes?