COMPSCI 70 Chapter Notes - Chapter 5: Eulerian Path, Mathematical Induction, Directed Graph
Document Summary
7:47 pm graph - a set of vertices and edges (simple path) - a sequence of edges where all vertices and edges appear once. All vertices visited are all distinct (no repeated edges) (a sequence of edges ( where is distinct cycle - a path where all vertices and edges visited are distinct except for the starting and ending vertex. For there to be a cycle between two vertices, there must be 2 ways to get from the starting to the ending vertex walk - a path with repeated vertices. Simple paths are a subset of walks (walks can contain no repeated vertices) tour - a walk which starts and ends at the same vertex. Connected and unconnected graphs connected graph - a graph that has a path between any 2 distinct vertices. Any graph always consists of a collection of connected components (even disconnected graphs)