fig directed graph only in fig we can move from vertex to vertex along the edge ( , )but we cannot move from vertex to at least not without going through some other verticesbecause the edge ( , is not in the set path in graph is series of edgesnone repeatedthat can be traversed in order to travel from one vertex to another in graph cycle in graph is path which begins and ends with the same vertex the last covered trees in computer science now armed with some notation from graph theory we can give formal definition of tree tree is directedconnected acyclic graph an acyclic graph is graph without any cycles sometimes in graph theory tree is defined as an acyclic connected graph dropping the requirement that it be directed graph in this casea tree may be defined as graph which is fully connectedbut has only one path between any two vertices both directed and undirected graphs can be used to model many different kinds of problems the graph in fig might represent register allocation in cpu the vertices could represent symbolically named registers and two registers that were both in use at the same time would have an edge between them the question that might be asked is"how many physical registers of the machine are required for the symbolic registers of this computation?it turns out that register allocation and map coloring represent the same problem when we abstract away the detailsthe problem boils down to graph coloring problem an answer to "how many colors are required to color the map?would answer "how many physical registers are required for this computation?and vice-versa weighted graph is graph where every edge has weight assigned to it more formallya weighted graph ( , ,wis graph with the given set of verticesvand edgese in additiona weighted graph has weight functionwthat maps edges to real numbers so the signature of is given by we real weighted graphs can be used to represent the state of many different problems for instancea weighted graph might provide information about roads and intersections cost/benefit analysis can sometimes be expressed in terms of weighted graph the weights can represent the available capacity of network connections between nodes in network this copy belongs to 'acha