Review Vocabulary

23

Chinese postman problem The problem of finding a circuit on a graph that covers every of the graph at least once and that has the shortest possible length. (p. 14)

Circuit A path that starts and ends at the same vertex. (p. 6)

Connected graph A graph wherein it is possible to reach any vertex from any specified starting vertex by traversing edges. (p. 11)

Digraph A graph in which each edge has an arrow indicating the direction of the edge. Such directed edges are appropriate when the relationship is “one-sided” rather than symmetric (for instance, one-way streets as opposed to regular streets). (p. 20)

Edge A link joining two vertices in a graph. (p. 6)

Euler circuit A circuit that traverses each edge of a graph exactly once. (p. 8)

Eulerizing Adding new edges which duplicate existing edges to a connected graph so as to make a graph that possesses an Euler circuit. (p. 16)

Graph A mathematical structure in which points (called vertices) are used to represent things of interest and in which links (called edges) are used to connect vertices, denoting that the connected vertices have a certain relationship. (p. 6)

Management science A discipline in which mathematical methods are applied to management problems in pursuit of optimal solutions that cannot readily be obtained by common sense. (p. 5)

Operations research (OR) Another name for management science. (p. 5)

Optimal solution When a problem has various solutions that can be ranked in preference order (perhaps according to some numerical measure of “goodness”), the optimal solution is the best-ranking solution. (p. 5)

Path A connected sequence of edges in a graph. (p. 6)

Valence (of a vertex) The number of edges touching that vertex. (p. 10)

Vertex A point in a graph where one or more edges end. (p. 6)