[Overview] [Previous] [Next]
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