第1章图论简介.ppt

1.图论问题的起源、发展及应用 18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？” 七桥问题的分析 七桥问题看起来不难，很多人都想试一试，但没有人找到答案 .后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想. Euler把南北两岸和四个岛抽象成四个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图: 欧拉的结论 欧拉指出:一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是: 1)图是连通的,即任意两点可由图中的一些边连接起来; 2)与图中每一顶点相连的边必须是偶数. 由此得出结论:七桥问题无解. 欧拉由七桥问题所引发的研究论文是图论的 开篇之作,因此称欧拉为图论之父. 4.图的作用 图是一种表示工具.改变问题的描述方式,往 往是创造性的启发式解决问题的手段.一种描述 方式就好比我们站在一个位置和角度观察目标, 有的东西被遮挡住了,但如果换一个位置和角度, 原来隐藏着的东西就可能被发现.采用一种新的 描述方式,可能会产生新思想.图论中的图提供 了一种直观,清晰表达已知信息的方式.它有时 就像小学数学应用题中的线段图一样,能使我们 用语言描述时未显示的或不易观察到的特征、 关系,直观地呈现在我们面前,帮助我们分析和 思考问题,激发我们的灵感. 5.图的广泛应用 图的应用是非常广泛的,在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络,如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等.还有许多看不见的网络,如各种关系网,像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等,这些网络都可以归结为图论的研究对象 ----图.其中存在大量的网络优化问题需要我们解决.还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题. 6.基本的网络优化问题 基本的网络优化问题有:最短路径问题、最小生成树问 题、最大流问题和最小费用问题.图论作为数学的一个 分支,已经有有效的算法来解决这些问题.当然这当中 的有些问题也可以建立线性规划的模型,但有时若变量 特别多,约束也特别多,用线性规划的方法求解效率不 高甚至不能在可忍受的时间内解决.而根据这些问题的 特点,采用网络分析的方法去求解可能会非常有效.例 如,在1978年,美国财政部的税务分析部门在对卡特尔 税制改革做评估的过程中,就有一个100,000个约束以 上,25,000,000个变量的问题,若用普通的线性规划求 解,预计要花7个月的时间.他们利用网络分析的方法, 将其分解成6个子问题,利用特殊的网络计算机程序,花 了大约7个小时问题就得到了解决. 图论中的经典算法与现代智能算法结合解决NP难题 TSP是一个典型的NP问题，针对该问题很多情况下的求 解，目前有很多智能算法，如遗传算法、神经网络、蚁群算 法、免疫算法和粒子群算法等。在利用这些算法求解TSP时， 有时为了降低时间复杂度和提高精确度，会同时使用图论中 的一些经典算法，如迪克斯曲拉算法、Floy算法等。此外，在 路由器的选址问题上，也常常利用图论中的一些经典算法。 本学期主要内容 第一章至第五章 平时成绩要求:写一篇3000字左右关于图论的 文章,主要是用图论知识解决一个实际问题. 文章包括以下几个部分 1.文题 2.摘要 3.关键词(3-5个) 4.正文 5.结论(一般要有运行结果及对结果的分析) 6.参考文献(需在文中标出,5-8个) 文章用A4打印,并加盖封面(上面有姓名,学号). 由于后续学习的需要,我们补充离散数学 中的一些基本内容:关系与函数. 预备知识 二元关系 复习集合中的几个定义 幂集、集合的（对称）差、广义交与并等。 定义1.9.设R为二元关系,A是集合 (1)R在A上的限制记为R?A,其中R?A={x,y∣xRy?x?A} (2)A在R下的像记作R[A],其中R[A]=ran(R?A). 显然有: R?A?R, R[A]?ranR. 例1.11.设R={1,2,1,3,2,2,2,4,3,2},则 R?{1}= R??= R?{2,3}= R?[{1}]= R?[?]= R?[{3}]= 第一章 图的基本概念(1) 定义1 图 图G是一个三元组,记作 其中(1)V(G)={v1,v2,…,vn}, 称为图G的结点集. (2)E(G)={e1,e2,…,em}是G的边集合,其中ei为 {vj,vt}或v