哈密頓( Hamilton) 周遊世界问題 正十二面体有二十个顶点 表不世界上20个城市 各经每个城市一次 最后返回原地 始點 投影至平面→ 圖十二 哈密頓路径至今尚无有效方法來解決!
哈密頓（Hamilton） 周遊世界问題 哈密頓路径至今尚无有效方法來解決！ 正十二面体有二十个顶点 表示世界上20个城市 各经每个城市一次 最后返回原地 投影至平面→
最短路径问題 (Shortest Path Problem 最快的 routing 最快航線 3 3 090 2 g
最短路径问題 (Shortest Path Problem) A B C D E F G 2 1 3 1 2 3 1 3 3 3 最快航線 最快的routing
最短路径算法→ Dijkstra算法 可以求出從某一点到图上其他任一点的最短路径 2704 arent distance BO D BWI l44 DEW JFK匚BW 184 (SFO 12s8 1391 LAX 337 MIA□Bw 946 ORD BWI 621 (LA 1235 1121 PVD AMIA SFO 2342
最短路径算法→Dijkstra算法 ◼ 可以求出從某一点到图上其他任一点的最短路径
走迷宫与深度优先搜索 Depth-First Search) 直往前走 碰壁就回头換条路找 沿途要记录下走过的路线 老鼠走迷宮→深度优先搜索
走迷宫与深度优先搜索 (Depth-First Search) 老鼠走迷宮→深度优先搜索 一直往前走 碰壁就回头換条路找 沿途要记录下走过的路线
Some graph-processing problems Path. Is there a path between s to t? Shortest path. What is the shortest path between s and t? Longest path. What is the longest simple path between s and t? Cycle. Is there a cycle in the graph? Euler tour. Is there a cycle that uses each edge exactly once? Hamilton tour. Is there a cycle that uses each vertex exactly once? Connectivity. Is there a way to connect all of the vertices? MST What is the best way to connect all of the vertices? Biconnectivity. Is there a vertex whose removal disconnects the g raph? Planarity. Can you draw the graph in the plane with no crossing edges? First challenge: Which of these problems is easy? difficult? intractable?
Some graph-processing problems ◼ Path. Is there a path between s to t? ◼ Shortest path. What is the shortest path between s and t? ◼ Longest path. What is the longest simple path between s and t? ◼ Cycle. Is there a cycle in the graph? ◼ Euler tour. Is there a cycle that uses each edge exactly once? ◼ Hamilton tour. Is there a cycle that uses each vertex exactly once? ◼ Connectivity. Is there a way to connect all of the vertices? ◼ MST. What is the best way to connect all of the vertices? ◼ Biconnectivity. Is there a vertex whose removal disconnects the graph? ◼ Planarity. Can you draw the graph in the plane with no crossing edges? First challenge: Which of these problems is easy? difficult? intractable?