Understanding the Sorted Edges Algorithm

The video tutorial introduces the Sorted Edges Algorithm, also known as the Cheapest Link Algorithm, used to find the optimal Hamiltonian circuit with the lowest cost. It outlines the steps of the algorithm and recaps previous lessons on Hamiltonian circuits using different algorithms. The tutorial demonstrates the application of the Sorted Edges Algorithm to find and compare different circuits, emphasizing the importance of selecting edges with the least weight while avoiding conditions that would create incomplete circuits or vertices with a degree of three. The video concludes with an additional example and a reminder that the Sorted Edges Algorithm may not always yield the optimal solution.

What is another name for the Sorted Edges Algorithm?

• Repeated Nearest Neighbor Algorithm

• Brute Force Algorithm

• Cheapest Link Algorithm

• Nearest Neighbor Algorithm

Which algorithm found the Hamiltonian circuit with a total weight of 19 in past lessons?

• Brute Force Algorithm

• Cheapest Link Algorithm

• Nearest Neighbor Algorithm

• Sorted Edges Algorithm

What is the first step in the Sorted Edges Algorithm?

• Select any random edge

• Select the edge with the second lowest weight

• Select the cheapest unused edge

• Select the edge with the highest weight

What condition must be avoided when adding an edge in the Sorted Edges Algorithm?

• Creating a circuit with all vertices

• Giving a vertex degree two

• Creating a circuit that doesn't contain all vertices

• Adding an edge with a weight of zero

In the Sorted Edges Algorithm, what happens if two edges have the same weight?

• Only one edge can be used

• Both edges are ignored

• Two possible circuits may be formed

• The edge with the higher degree is chosen

What is the total weight of the circuit starting with vertex D in the first example?

• 25

• 23

• 21

• 19

Which edge cannot be used because it would give vertex E a degree three?

• Edge E, A

• Edge E, B

• Edge A, D

• Edge C, D

In the final example, which edge completes the circuit?

• Edge D, E

• Edge B, D

• Edge C, E

• Edge A, B

What is the total weight of the circuit in the final example?

• 40

• 35

• 45

• 30

What is the correct order of vertices in the circuit starting at vertex A in the final example?

• A, C, B, E, D, A

• A, B, C, D, E, A

• A, E, D, C, B, A

• A, D, E, B, C, A