第四章 图论的介绍.pptVIP

第四章 图论的介绍 哥尼斯堡七桥问題(Bridges of Koenigsberg) 欧拉路径解決哥尼斯堡七桥问題 实际生活中的图论Graph Model 电路模拟 交通网络 交通网络：自驾车从广州到拉萨最小花费的路线是什么？花费：金钱、时间、风景。解答这个问题，我们需要知道连接两个城市路线的相关信息。电话通讯网络：我们对其实际的互联结构感兴趣，因为我们要布置网线设置交换设备以便有效控制流量。计算机网络：站点与站点之间是否连通？是否有些站点或者线路特别重要（被破坏会导致大面积网络瘫痪）？另一个例子，金融机构股票的买入/卖出。连接表示两个客户之间的现金转移，利于加强对市场本质的理解。 有向图 社会网路 蛋白质交互网路 美国西部的电力传输网路 因特网 更多的应用 Hypertexts 网页包含到其他网页的超链接。整个Web是一个图. 有哪些信誉好的足球投注网站引擎需要图处理算法。 Matching 职位招聘，如何有效将职位与应聘者匹配？ Schedules 工程项目的任务安排，如何满足限制条件，并在最短时间内完成？ Program structure 大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效率。 图的应用 图论问题及其算法 哈密頓（Hamilton）周游世界问題 最短路径问題 (Shortest Path Problem) 最短路径算法?Dijkstra算法 可以求出从某一点到图上其他任一点的最短路径 走迷宫与深度优先有哪些信誉好的足球投注网站(Depth-First Search) 一些图论的问题 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? 图论的概念 什么是图？ 图论的术语 再来一些术语 有向图(Digraph) 加权图(Weighted Graph) 生成树(Spanning Tree) 可运用生成树的实例 一些特殊的图 完全图 Complete graphs 任意两点之间都有一条边与其相连的图称为完全图，以Kn 來表示，n为顶点数 平面图实例 8个顶点(V=8) 12条边 (E=12) 6个面 (F=6) 8-12+6=2 更多平面图实例 树 Trees 树(tree):连通无简单回路无向图 若有n个顶点，則有n-1条边 任两点之间仅有一条路径 生成树 (spanning tree):包括图中所有的顶点，并且是一棵树 * * 二部图（偶图） (Bipartite graphs) 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i, j）所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二部图。 如果A,B中任意两个点都有一条边相连，则称这样的二部图为完全二部图 完全二部图 K2,3 二部图 * * 平面图 (Planar graphs) 如果一个图能在平面上展开，并且任意两条边不交叉，则这样的图称为平面图 Planar: = NOT Planar: A connected graph G Spanning trees of G tree * * 能不能走过每一个桥刚好一次并且回到原來的地方？ 原來是一笔画问题啊！ 数学家欧拉(Euler, 1707-