Chapter 1 Flashcards
Circuit
A path that starts and ends at the same vertex.
Path
A connected sequence of edges in a graph
Euler’s Circuit
A circuit that traverses each edge of a graph exactly once.
Edge
A link joining two vertices in a graph.
Connected Graph
A graph is connected if it is possible to reach any vertex from any specified stating vertex by traversing.
Even Valence
When each and every vertex has an even number valence.
A graph is a Eurler’s Circuit if…
it is connected and has even valence.
Nearest Neighbor Algorithm
An algorithm for attempting to solve the TSP that begins at a home vertex and visits next that vertex not already visited that can be reached most cheaply. When all other vertices have been visited, the tour returns to home. This method may not give the optimal answer.
Sorted-Edges Algorithm
An algorithm for attempting to solve the TSP where the edges added to the circuit being built up are selected in order of increasing cost, but no edge is chosen that would prevent a Hamiltonian circuit from forming (don’t prematurely close the circuit or put 3 edges are joined at one vertex). These edges must all be connected at the end, but not necessarily at earlier stages. The tour obtained may not have the lowest possible cost.
Simple Interest Formula
I = PRT
Simple-Interest Amount Formula
A = P(1 + RT)
Compound Interest Formula
A = P(1 + r/m)^mt
Continuous Compounding Formula
A = Pe^rt
Payment Formula
d = a(r/m) divided by ( 1+ r/m)^mt - 1
Savings Formula
A = [d(1 + r/m)^mt - 1] / (r/m)