Graph Theory Words

2. this type of circuit covers every edge
3. If a connected graph has any _____ vertices, then G cannot have an Euler circuit
4. founder of graph theory
6. a term for a vertex that is all alone :( (not connected to any other vertices)
8. this type of graph can be drawn so that none of the edges overlap
9. when a processor in a scheduling graph has no available task
12. Euler's theorem says that every graph has a ______ number of odd vertices
14. this type of circuit visits every vertex
16. a line that connects the dots on a graph
17. nearest _________ algorithm takes the edge of least out of the vertex we are at
19. a route that does not travel any edge twice, and starts and ends at the same vertex
20. any planar graph can be colored in with this many colors (or fewers)
21. ___________ link algorithm takes the edge of least cost, regardless of where it is. Avoid closing circuit until all vertices are visited
22. the name for an edge that, if it was deleted, would disconnect the graph

1. in a directed graph, the number of edges head out of a vertex
5. an edge that starts and ends at the same vertex
7. two vertices are __________ if there is an edge joining them.
9. in a directed graph, the number of edges heading into a vertex
10. an alternate term for a directed graph
11. in love with catherine disney; was not allowed to marry her
13. a node on a graph. Often represents people, cities, or states.
15. the greek letter associated with the chromatic number of a graph
18. a route that does not travel any edge twice, but does NOT have to start and end at the same vertex