1.4 Paths and Connected Graphs

A path is a sequence of edges, e.g. v1,v2,v2,v3,,vn-1,vn(v_{1},v_{2}),(v_{2},v_{3}),\cdots,(v_{{n-1}},v_{n}). This path connects vertices v1v_{1} and vnv_{n}. The path may also be represented by the vertex sequence v1,v2,v3,,vn-1,vnv_{1},v_{2},v_{3},\cdots,v_{{n-1}},v_{n}. The path begins at vertex v1v_{1} passes through vertices v2,v3,,vn-1v_{2},v_{3},\cdots,v_{{n-1}} and ends at vertex vnv_{n}.

The number of edges that comprise a path is its length. A path is simple if all of the vertices on a path are distinct (with the possible exception of the first and last vertices).

If some path connects each pair of vertices in GG, then GG is a connected graph.

Connected digraphs are classified as either weakly connected or strongly connected. A strongly connected digraph has a directed path that connects all the vertices in the graph. All the vertices of a strongly connected digraph must have an in-degree of at least one.

A weakly connected digraph has has an undirected path that connects all the vertices in the graph. All the vertices of a weakly connected digraph must have either an in-degree or out-degree of at least one.