行遍性问题 一、中国邮递员问题 (一)欧拉图 (二)中国邮递员问题 二、推销员问题 (一)哈密尔顿图 (二)推销员问题 三、建模案例:最佳灾情巡视路线

8.1 图论问题 歌尼斯堡七桥问题 哈密尔顿回路问题 中国邮路问题 8.2 算法复杂性问题 8.3 计算机智能问题 8.4 并发控制问题

•几十年来图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。•在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。•这里主要讨论图的基本概念和算法,为今后的学习和研究打下基础。本章首先给出图、简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图

图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼 斯堡的七座桥”。1847年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857 年,凯莱在计数烷CnH2n+2的同分异构物时,也发现了“树”。哈密尔顿于1859年提 出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈,近几十年 来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和 方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会 学等学科中