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. 

