would be the shortest set of pipes connecting all the locations there is also the famous travelling salesman problem which involves finding the shortest route through the structure that visits each city precisely once graph terminology the kind of structure in the above figure is known formally as graph graph consists of series of nodes (also called vertices or points)displayed as nodesand edges (also called lineslinks orin directed graphsarcs)displayed as connections between the nodes there exists quite lot of terminology that allows us to specify graphs preciselya graph is said to be simple if it has no self-loops ( edges connected at both ends to the same vertexand no more than one edge connecting any pair of vertices the remainder of this will assume thatwhich is sufficient for most practical applications if there are labels on the edges (usually non-negative real numbers)we say that the graph is weighted we distinguish between directed and undirected graphs in directed graphs (also called digraphs)each edge comes with one or two directionswhich are usually indicated by arrows think of them as representing roadswhere some roads may be one-way only or think of the associated numbers as applying to travel in one way onlysuch as going up hill which takes longer than coming down an example of an unweighted digraph isa and an example of weighted digraphbecause it has labels on its edgesis in undirected graphswe assume that every edge can be viewed as going both waysthat isan edge between and goes from to as well as from to the first graph given at the beginning of this is weighted and undirected path is sequence of nodes or vertices vn such that vi and vi+ are connected by an edge for all < < note that in directed graphthe edge from vi to vi+ is the one which has the corresponding direction circle is non-empty path whose first vertex is the same as its last vertex path is simple if no vertex appears on it twice (with the exception of circlewhere the first and last vertex may be the same this is because we have to 'cut openthe circle at some point to get pathso this is inevitable