# Shared Flashcard Set

## Details

College Math
Urban Services
20
Mathematics
01/30/2016

Term
 Graph
Definition
 A finite set of dots and connecting links.
Term
 Vertices
Definition
 Dot on a graph; Labeled with an uppercase letter. (Plural: vertex)
Term
 Edge
Definition
 The link between the vertices. Edges are named by listing the vertices connected.
Term
 Path
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
 Circuit
Definition
 A path that begins and ends at the same vertex.
Term
 Accidental Crossings
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
 Are all circuits a path?
Definition
 Yes.
Term
 Are all paths circuits?
Definition
 No.
Term
 Euler Circuit
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
 Valance
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
 Connected Graph
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
 Chinese Postman Problem
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
 Eulerizing The Graph
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
 Rectangular Network
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
 Hamiltonian Circuit
Definition
 A tour that starts at a vertex of a graph and visits each vertex once returning to the starting vertex.
Term
 Weights
Definition
 A number assigned to an edge of a graph that can be considered a cost, distance, or time associated with that edge.
Term
 Brute-Force Method
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
 Complete Graph
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
 Sorted-edges Algorithm
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.
Supporting users have an ad free experience!