MA 103 Chapter Notes - Chapter 5-6: Travelling Salesman Problem, Hamiltonian Path, Eulerian Path
Document Summary
Graph: a collection of dots, called vertices, and line segments, called edges, in which each edge is required to have a vertex at each end. Degree of a vertex: the number of edges that meet there. Isolated vertex: not connected to any other vertex by an edge. Adjacent edges: edges that have a common vertex. Loop: an edge with both ends at the same vertex. Connected: a graph is connected if there is a path going from any vertex to any other vertex. Disconnected: a graph is disconnected if it is not connected. Bridge: in a connected graph, an edge is a bridge if when we remove it, the graph becomes disconnected. Path: a sequence of adjacent edges with no edge included more than once. Circuit: a path that begins and ends at the same vertex. Euler path: a path that uses every edge exactly once. Euler circuit: a circuit that uses every edge exactly once.
