§1 图的基本概念 §2 路与回路 §3 图的矩阵表示 §4 欧拉图和汉密尔顿图 §5 平面图 §6 树与生成树

–平面图的基本概念 –欧拉公式 –平面图的判断 –平面图的对偶图 –顶点着色及点色数 –地图的着色与平面图的点着色 –边着色及边色数

7.1 图的概念/Introduction of Graph 7.2 图的术语/Graph Terminology 7.3 图的表示与同构/ Representing Graph and Graph Isomorphism 7.4 连通性/Connectivity 7.5 欧拉道路与哈密尔顿道路/ Euler and Hamilton Paths 7.6 最短道路问题/Shortest Path Problem 7.7 平面图/Planar Graphs 7.8 图的着色/Graph Coloring

§7.1 平面图的概念 §7.2 欧拉公式 §7.3 平面图的判断 §7.4 平面图的对偶图 §7.5 平面图的面染色和四色猜想

8.4 平面图 ▪ 平面图与平面嵌入 ▪ 平面图的面、有限面、无限面 ▪ 面的次数 ▪ 极大平面图 ▪ 极小非平面图 ▪ 欧拉公式 ▪ 平面图的对偶图

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

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

一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题

一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题