Circuits Quiz

What makes a path an euler circuit?

even valent vertices, connected graph, starts and ends in the same place, and uses each edge only once

What makes a path a circuit?

The graph is connected and starts and ends in the same place

What makes a path a hamiltonian circuit?

start and end at the same vertex and each vertex is only visited once

How would you solve a vacation planning problem?

Generate all possible hamiltonian circuits, add up the distances of the edges for each possible circuit, then choose the circuit of minimum distance.

Describe the method of trees

Select a starting vertex, then build a diagram showing the next possible location until the diagram is back at the starting vertex

How would you solve a traveling salesman problem?

Use the nearest neighbor method (start at home, then visit the nearest vertex, repeat until all are visited) or the sorted edges method (arrange edges in increasing order, choose the least cost edge that doesn’t have 3 used edges meeting at a vertex and uses all vertices)