graphs concerning these bridgesit was asked whether anyone could arrange route in such way that he would cross each bridge once and only once -"the solution of problem relating to the geometry of position, euler informallya graph is set of vertices and connected by edges formallya directed graph is set of vertices and set of edges given an edge (uv)the vertex is its sourceand is its sink graphs are often decoratede by adding lengths to edgesweights to verticesa start vertexetc directed graph can be depicted pictorially as in figure path in directed graph from to vertex is sequence of vertices hv vn- where uvn- vand each (vi vi+ is an edge the sequence may consist of single vertex the length of the path hv vn- is intuitivelythe length of path is the number of edges it traverses if there exists path from to vv is said to be reachable from for examplethe sequence hacedhi is path in the graph represented in figure figure directed graph with weights on edges directed acyclic graph (dagis directed graph in which there are no cyclesi paths which contain one or more edges and which begin and end at the same vertex see figure on the following page for an example of directed acyclic graph vertices in dag which have no incoming edges are referred to as sourcesvertices which have no outgoing edges are referred to as sinks topological ordering of the vertices in dag is an ordering of the vertices in which each edge is from vertex earlier in the ordering to vertex later in the ordering an undirected graph is also tuple (ve)howevere is set of unordered pairs of vertices graphicallythis is captured by drawing arrowless connections between verticesas in figure