Question: 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?