graphs directed graph is one in which you must follow the minimum spanning tree you must go from vertex to vertex to vertex and so on you can go in only one direction from one given vertex to another you can go in only one direction on any given path if an adjacency matrix has rows { , , , }{ , , , }{ , , , }and { , , , }what is the corresponding adjacency list minimum spanning tree is graph in which the number of edges connecting all the vertices is as small as possible the number of edges is equal to the number of vertices all unnecessary vertices have been removed every combination of two vertices is connected by the minimum number of edges how many different minimum spanning trees are there in an undirected graph of three vertices and three edges an undirected graph must have cycle if any vertex can be reached from some other vertex the number of paths is greater than the number of vertices the number of edges is equal to the number of vertices the number of paths is less than the number of edges is graph with no cycles can minimum spanning tree for an undirected graph have cycles true or falsethere may be many correct topological sorts for given graph topological sorting results in vertices arranged so the directed edges all go in the same direction vertices listed in order of increasing number of edges from the beginning vertex vertices arranged so precedes bwhich precedes cand so on vertices listed so the ones later in the list are downstream from the ones earlier