sec terminology and representations figure an undirected graph with three connected components vertices and form one connected component vertices and form second connected component vertex by itself forms third connected component subgraph is formed from graph by selecting subset vs of ' vertices and subset es of ' edges such that for every edge in es both of its vertices are in vs an undirected graph is connected if there is at least one path from any vertex to any other the maximally connected subgraphs of an undirected graph are called connected components for examplefigure shows an undirected graph with three connected components graph without cycles is called acyclic thusa directed graph without cycles is called directed acyclic graph or dag free tree is connectedundirected graph with no simple cycles an equivalent definition is that free tree is connected and has | edges there are two commonly used methods for representing graphs the adjacency matrix is illustrated by figure (bthe adjacency matrix for graph is |vx |varray assume that |vn and that the vertices are labeled from through vn- row of the adjacency matrix contains entries for vertex vi column in row is marked if there is an edge from vi to vj and is not marked otherwise thusthe adjacency matrix requires one bit at each position alternativelyif we wish to associate number with each edgesuch as the weight or distance between two verticesthen each matrix position must store that number in either casethe space requirements for the adjacency matrix are th(| | the second common representation for graphs is the adjacency listillustrated by figure (cthe adjacency list is an array of linked lists the array is |vitems longwith position storing pointer to the linked list of edges for vertex vi this linked list represents the edges by the vertices that are adjacent to vertex vi the adjacency list is therefore generalization of the "list of childrenrepresentation for trees described in section