Рефераты / Иностранные языки /

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

every point of the graph, with two possible exceptions, must be at the junction of an even number of lines. It is not hard to understand why a graph cannot have an Eulerian path unless it meets these conditions. All regions of the graph must be connected to one another if there is to be any path that traverses all the lines. Each point must have an even number of lines because half of them are required to reach the point and the other half to leave it. Two points with an odd number of lines can be allowed if they are chosen as the starting and finishing points of the path. Demonstrating that any graph that meets these conditions actually has an Eulerian path requires a somewhat more complicated argument, which we shall not present here, but Euler was able to give a rigorous proof. It is an easy matter to express Euler's solution to this problem in an algorithm that could be executed by a computer. The first requirement, connectivity, can be established by marking some point of the graph, then similarly marking all points connected to it by lines, then all the points connected to the newly marked points, and so on. The graph is connected if at the end all points have been marked. The second requirement is just as easily tested: the machine is instructed to examine each point of the graph and count the number of lines that terminate at that point. If no more than two of the points have an odd number of lines, the graph has an Eulerian path. The park at Koenigsberg met the first condition but not the second, and so there was no Eulerian tour of the seven bridges. Euler's method is unquestionably the more economical approach to the problem of Koenigsberg bridges: it requires that each point and line of the graph be listed just once, whereas the exhaustive search is not completed until every path that crosses all the bridges has been listed. The number of such paths is much larger than the number of points and lines in the graph. In that sense Euler's method is the better algorithm, but how much better? How can the difference be measured and how can one fell if the difference is significant? For a graph with only four points and seven lines both techniques are fast enough to be considered practical. Suppose, however, that more islands and bridges were added to the park, or in other words that more points and lines were added to graph. If the problem is being solved by Euler's method, each new point merely adds one item to the list of points that must be checked. If the paths are to be examined by exhaustive search, on the other hand, then with each new point and line the size of the list is multiplied by some factor. A moderate increase in the size of the graph results in an explosive increase in the number of paths. Ultimately the list of paths 'must become prohibitively long. In this comparison of the two solutions to Euler's problem there is the basis for a completely general method of evaluating the speed or practicality or efficiency of any algorithm. We imagine that the algorithm is supplied with larger and larger inputs, and we note the rate at which the execution time of the algorithm increases. In this way it is possible to make unequivocal judgments of algorithms. Exhaustive search not only is a slower method; in general it is too slow to be of any value. Euler's method remains practical for problems of essentially unlimited size. As the size of the graphs being examined increases, the lists produced by the method of
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ