chap graphs ( ( (cfigure examples of graphs and terminology (aa graph (ba directed graph (digraph(ca labeled (directedgraph with weights associated with the edges in this examplethere is simple path from vertex to vertex containing vertices and vertices and also form pathbut not simple path because vertex appears twice vertices and form simple cycle terminology and representations graph (veconsists of set of vertices and set of edges esuch that each edge in is connection between pair of vertices in the number of vertices is written | |and the number of edges is written | |ecan range from zero to maximum of | | |va graph with relatively few edges is called sparsewhile graph with many edges is called dense graph containing all possible edges is said to be complete graph with edges directed from one vertex to another (as in figure ( )is called directed graph or digraph graph whose edges are not directed is called an undirected graph (as illustrated by figure ( ) graph with labels associated with its vertices (as in figure ( )is called labeled graph two vertices are adjacent if they are joined by an edge such vertices are also called neighbors an edge connecting vertices and is written (uvsuch an edge is said to be incident on vertices and associated with each edge may be cost or weight graphs whose edges have weights (as in figure ( )are said to be weighted sequence of vertices vn forms path of length if there exist edges from vi to vi+ for < path is simple if all vertices on the path are distinct the length of path is the number of edges it contains cycle is path of length three or more that connects some vertex to itself cycle is simple if the path is simpleexcept for the first and last vertices being the same some graph applications require that given pair of vertices can have multiple edges connecting themor that vertex can have an edge to itself howeverthe applications discussed in this book do not require either of these special casesso for simplicity we will assume that they cannot occur