| A | B |
|---|
| algorithm | set of mechanical rules used for solution |
| approximate algorithm | produces good solutions "most" of the time |
| brute force algorithm | uses all HCs to find best solution |
| cheapest-link algorithm | produces one solution if weights not equal |
| complete graph | all vertices have direct connection to each other |
| weighted graph | each edge is assigned a number |
| efficient algorithm | # of steps grows in proportion to the input information |
| (n-1)!/2 | number of Hamiltonian subgraphs in a Kn graph |
| n(n-1)/2 | # of edges in a Kn graph |
| Hamiltonian Circuit(HC) | start and finish in the same place and pass through each vertex once |
| nearest neighbor algorithm | can produce many solution for same Kn |
| (n-1) | degree of each vertex in a Kn graph |
| optimal solution | generally requires brute force algorithm |
| TSP | traveling salesman problem |
| (n-1)! | # HCs in a Kn graph |
| repetitive nearest-neighbor algorithm | uses different starting points |
| Hamiltonian Subgraph | A graph showing one circuit and its mirror image |
| inefficient algorithm | # of steps needed for solution increases rapidly with additional vertices |
