path is sequence of alternating vertices and edges that starts at vertex and ends at vertex such that each edge is incident to its predecessor and successor vertex cycle is path that starts and ends at the same vertexand that includes at least one edge we say that path is simple if each vertex in the path is distinctand we say that cycle is simple if each vertex in the cycle is distinctexcept for the first and last one directed path is path such that all edges are directed and are traversed along their direction directed cycle is similarly defined for examplein figure (bosnw jfkaa dfwis directed simple pathand (laxua ordua dfwaa laxis directed simple cycle note that directed graph may have cycle consisting of two edges with opposite direction between the same pair of verticesfor example (ordua dfwdl ordin figure directed graph is acyclic if it has no directed cycles for exampleif we were to remove the edge ua from the graph in figure the remaining graph is acyclic if graph is simplewe may omit the edges when describing path or cycle cas these are well definedin which case is list of adjacent vertices and is cycle of adjacent vertices example given graph representing city map (see example )we can model couple driving to dinner at recommended restaurant as traversing path though if they know the wayand do not accidentally go through the same intersection twicethen they traverse simple path in likewisewe can model the entire trip the couple takesfrom their home to the restaurant and backas cycle if they go home from the restaurant in completely different way than how they wentnot even going through the same intersection twicethen their entire round trip is simple cycle finallyif they travel along one-way streets for their entire tripwe can model their night out as directed cycle given vertices and of (directedgraph gwe say that reaches vand that is reachable from uif has (directedpath from to in an undirected graphthe notion of reachability is symmetricthat is to sayu reaches if an only if reaches howeverin directed graphit is possible that reaches but does not reach ubecause directed path must be traversed according to the respective directions of the edges graph is connected iffor any two verticesthere is path is strongly connected if for any two vertices between them directed graph and of gu reaches and reaches (see figure for some examples subgraph of graph is graph whose vertices and edges are subsets of the vertices and edges of grespectively spanning subgraph of is subgraph of that contains all the vertices of the graph if graph is not connectedits maximal connected subgraphs are called the connected components of forest is graph without cycles tree is connected forestthat isa connected graph without cycles spanning tree of graph is spanning subgraph that is tree (note that this definition of tree is somewhat different from the one given in as there is not necessarily designated root