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.