12.5k views
4 votes
15. (GT2) Which of the path names belowdescribes a Hamilton circuit for the graph?A. AEJIBCFHGDB. AEJIBACFIHGEDCBFHJGDAC. AEJIBADGHFCAD. ABIJEDGHFCA

15. (GT2) Which of the path names belowdescribes a Hamilton circuit for the graph-example-1
User Dadep
by
7.5k points

1 Answer

5 votes

Ok, so:

Let's see that a Hamiltonian circuit is a circuit that visits every vertex once with no repeats. A Hamiltonian circuir also visits every vertex once with no repeats, it must start and end at the same vertex.

So, we're going to see all the options, and see which one could be or not a Hamilton circuit. Right?

So, let's start with A.

A. AEJIBCFHGD

Notice that according this, the circuit starts in A.

We have to make sure that this path doesn't repeat any vertex.

So, let's follow the path!

If we look at the path, we can affirm that it is not a hamiltonian circuit, because it doesn't start and finish at the same vertex.

B and C, can't be a Hamiltonean circuit, because if you look, there are a lot of repetitions in the path, and this can't happen.

But if we look at D, ABIJEDGHFCA, we notice that the two conditions are right, because it doesn't repeat any vertex, and it starts and finishes at the same vertex.

So, answer is D.

User David Goshadze
by
7.3k points