Term
|
Definition
| A finite set of dots and connecting links. |
|
|
Term
|
Definition
| Dot on a graph; Labeled with an uppercase letter. (Plural: vertex) |
|
|
Term
|
Definition
| The link between the vertices. Edges are named by listing the vertices connected. |
|
|
Term
|
Definition
| A connected sequence of edges showing a root on the graph that starts at a vertex and ends at a vertex. Named by listing vertices in the order they are used. |
|
|
Term
|
Definition
| A path that begins and ends at the same vertex. |
|
|
Term
|
Definition
| Occur when two edges cross but there is no vertex. Named by stating the pair of edges that cross. (Ex: AD and BC) |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
A circuit that covers an edge of a graph exactly once.
- Begins and ends at the same vertex.
- Vertices can be repeated, edges cannot. |
|
|
Term
|
Definition
Valence of a vertex is the number of edges meeting at the vertex.
- The number of edges is half of the total valence.
- The total valence is double the number of edges. |
|
|
Term
|
Definition
A graph is connected if for every pair of its vertices there is at least one path connecting the two vertices.
- Must be able to trace the graph without lifting your pencil. (It's okay to repeat an edge.) |
|
|
Term
|
Definition
| The problem of finding a circuit of a graph that covers every edge of the graph at least once (allows for repeated edges) and has the shortest possible length. |
|
|
Term
|
Definition
Adding edges that duplicate existing edges to make all of the valences even.
- Can only Eulerize a connected graph.
- The end result has a Euler Circuit. |
|
|
Term
|
Definition
| A street network composed of a series of rectangular blocks that form a large rectangle made up of so many blocks high (rows) by so many blocks wide (columns). |
|
|
Term
|
Definition
| A tour that starts at a vertex of a graph and visits each vertex once returning to the starting vertex. |
|
|
Term
|
Definition
| A number assigned to an edge of a graph that can be considered a cost, distance, or time associated with that edge. |
|
|
Term
|
Definition
1. Generate all of the possible Hamiltonian circuits. (Method of Trees)
2. Find the total cost of each circuit.
3. Choose the circuit with the smallest cost. |
|
|
Term
|
Definition
| A graph is complete if there is exactly one edge between each pair of vertices in the graph. |
|
|
Term
| Nearest Neighbor Algorithm |
|
Definition
| Repeatedly select the closest neighboring vertex (smallest weight) not yet visited in the circuit and return to the starting vertex. |
|
|
Term
|
Definition
1. Sort the edges of a complete graph from smallest to largest cost.
2. Select an edge that has not been previously chosen of least cost that:
A. Never requires 3 used edges to meet at a vertex.
B. Never select an edge that closes the circuit without visiting all of the vertices. |
|
|
