MATH 141 Chapter Notes - Chapter Chapter 1: Snowplow, Route Inspection Problem, Eulerian Path
13 Oct 2017
School
Department
Course
Professor
Document Summary
A graph is a finite set of vertices (dots) connected by edges. The degree (valence) of a vertex is the number of edges incident to the vertex. can you have a graph with these vertex degrees: 5, 4, 3, 2, 1, 0? or with these. Theorem: the sum over all vertices of the degrees = 2 * number of edges. Can you draw a graph with 5 vertices where the degree of each vertex is 3? (hint: what would be the sum over all the vertices of the degrees?) A path is a connected sequence of edges. Give a path in the graph from a to d. A graph is connected if and only if for every pair of vertices there is a path in the graph between them. A circuit (cycle) is a path that starts and ends at the same point. An eulercircuit is a circuit that traverses each edge exactly once.
