knapsack and graph optimization problems graphs are typically used to represent situations in which there are interesting relations among the parts the first documented use of graphs in mathematics was in when the swiss mathematician leonhard euler used what has come to be known as graph theory to formulate and solve the konigsberg bridges problem konigsbergthen the capital of east prussiawas built at the intersection of two rivers that contained number of islands the islands were connected to each other and to the mainland by seven bridgesas shown on the map below for some reasonthe residents of the city were obsessed with the question of whether it was possible to take walk that crossed each bridge exactly once euler' great insight was that the problem could be vastly simplified by viewing each separate landmass as point (think "node"and each bridge as line (think "edge"connecting two of these points the map of the town could then be represented by the graph to the right of the map euler then reasoned that if walk were to traverse each edge exactly onceit must be the case that each node in the middle of the walk ( any node except the first and last node visitedmust have an even number of edges to which it is connected since none of the nodes in this graph has an even number of edgeseuler concluded that it is impossible to traverse each bridge exactly once map of konigsberg arrows point to bridges euler' simplified map of greater interest than the konigsberg bridges problemor even euler' theorem (which generalizes his solution to the konigsberg bridges problem)is the whole idea of using graph theory to help understand problems for exampleonly one small extension to the kind of graph used by euler is needed to model country' highway system if weight is associated with each edge in graph (or digraphit is called weighted graph using weighted graphsthe highway system can be represented as graph in which cities are represented by nodes and the highways connecting them as edgeswhere each edge is labeled with the distance between the two nodes more generallyone