eulerpathsandcircuits(更新版)
【正文】 it ? If at one node number in = number out +1 and at one other node number in = number out 1, and all other nodes have number in = number out, then there is an Euler path. Path, circuit, or neither…? Hamilton Circuit ? Given a graph, when is there a circuit passing through each node exactly one time? ? Hard to solve – only general algorithm known is to try each possible path, starting at each vertex in turn. ? For there are n! possible trials. nKThe Traveling Salesman Problem ? A salesman needs to visit n cities and return home. What is the cheapest way to do this? 170 340 279 459 197 346 Cinn Atl Den Bos TSP ? The traveling salesman problem is NP – plete. ? Practically, this means that there is no know polynomialtime algorithm to solve the problem – and there is unlikely to be one.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1