Adjacent vertices: A pair of vertices that determine an edge are “adjacent”
vertices.
In the graph shown above, vertex ‘e’ is an “Isolated vertex”, ‘a’ and ‘b’ are
adjacent vertices, vertices ‘a’ and ‘d’ are not adjacent.
Path: A path in a graph G consists of a pair (V, E) of sequences.
Circuit: A circuit is a path that begins and ends at the same vertex.
Simple Path: A path is called “simple” if no vertex appears more than once in
the vertex sequence.
Connected Graph: A graph is called “connected” if there is a path from any
vertex to any other vertex in the graph, otherwise, the graph is “disconnected”.
Components: If the graph is disconnected, the various connected pieces are
called the “components” of the graph.
The above two graphs are examples of connected graphs.
The above two graphs are examples of disconnected graphs.
16
Theory of Automata, Formal Languages and Computation
vertices.
In the graph shown above, vertex ‘e’ is an “Isolated vertex”, ‘a’ and ‘b’ are
adjacent vertices, vertices ‘a’ and ‘d’ are not adjacent.
Path: A path in a graph G consists of a pair (V, E) of sequences.
Circuit: A circuit is a path that begins and ends at the same vertex.
Simple Path: A path is called “simple” if no vertex appears more than once in
the vertex sequence.
Connected Graph: A graph is called “connected” if there is a path from any
vertex to any other vertex in the graph, otherwise, the graph is “disconnected”.
Components: If the graph is disconnected, the various connected pieces are
called the “components” of the graph.
The above two graphs are examples of connected graphs.
The above two graphs are examples of disconnected graphs.
16
Theory of Automata, Formal Languages and Computation