[Overview] [Previous] [Next]
Graphs

Importance: Automata are graphs.
 A graph consists of two sets
 A set V of vertices (or nodes), and
 A set E of edges (or arcs).
 An edge consists of a pair of vertices in V.
If the edges are ordered, the graph is a digraph
(a contraction of "directed graph").
 A walk is a sequence of edges, where
the finish vertex of each edge is the start vertex of the next edge.
Example: (a, e), (e, i), (i, o), (o, u).
 A path is a walk with no repeated edges.
 A simple path is a path with no repeated vertices.
Copyright © 1996 by David Matuszek
Last modified Feb 2, 1996