### Discrete Math - Graph Theory Vocabulary

Mrs. Hamm

Review graph theory vocabulary by filling out the puzzle below.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Across
1.a percentage that indicates how good a tour is compared to the optimal tour
7.lines connecting the dots of the graph
9.set of dots in a graph
10.means the least cost, shortest distance, etc.
11.a circuit that passes through every edge of the graph once
12.an edge that connects a vertex back to itself
15.a set of procedural rules
17.drawings in which you can trace every line without lifting your pencil or retracing the lines
20.a value assigned to each edge
22.a path that includes every vertex of the graph once
23.a graph made of seperate components
24.the number of edges meeting at a vertex
25.a picture consisting of vertices, edges and loops
26.a path that passes through every edge of the graph once
Down
2.two vertices with an edge between them
3.any edge that if removed would cause the graph to become disconnected
4.a trip that starts and ends at a designated site and visits each of the other sites
5.a circuit that includes every vertex of the graph once
6.an algorithm that finds an Euler circuit or path
8.a trip that starts and ends at the same vertex (closed trip)
13.edges that share a common vertex
14.a graph in which you can get from any vertex to any other vertex along a path
16.two edges connecting the same pair of vertices
18.a graph in which every pair of distinct vertices is joined by an edge
19.number of edges in a path or circuit
21.a trip that ends at a different vertex than it began (open trip)

Use the "Printable HTML" button to get a clean page, in either HTML or PDF, that you can use your browser's print button to print. This page won't have buttons or ads, just your puzzle. The PDF format allows the web site to know how large a printer page is, and the fonts are scaled to fill the page. The PDF takes awhile to generate. Don't panic!

 Web armoredpenguin.com