1、济南大学离散数学第 7章 图 论离 散 数 学济南大学 信息科学与工程学院1济南大学离散数学第 7章 图7.1 图的基本概念7.2 路与回路7.3 图的矩阵表示7.4 汉密尔顿图和欧拉图 7.5 平面图 7.6 对偶图和着色 7.7 树7.8 根树2济南大学离散数学本章学习要求重点掌握 一般掌握 了解1图论的基本概念、基本方法基本算法3图论中的应用 2复杂问题的证明 3济南大学离散数学引例 1 哥尼斯堡七桥问题 1736年瑞士数学家列昂哈德 欧拉 (leonhard Euler)发表了图论的第一篇论文 “哥尼斯堡七桥问题 ”。这个问题是这样的： 哥尼斯堡 (Knigsberg)城市有一条横贯全
2、城的普雷格尔 (PreGel)河，城的各部分用七座桥连接，每逢假日，城中的居民进行环城的逛游，这样就产生一个问题，能不能设计一次 “逛游 ”，使得从某地出发对每座跨河桥走一次，而在遍历了七桥之后却又能回到原地。4济南大学离散数学gfabcde BCAD引例 1 哥尼斯堡七桥问题现实问题抽象成图若想完成逛游，需要添加几座桥，如何建？A BCD5济南大学离散数学引例 2 周游世界问题 1859年威廉 汉密尔顿爵士在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏，能不能在图中找到一条回路，使它含有这个图的全部结点？ 他把结点看作是一座城市，联结两个结点的边看成是交通线，于是它的问题是 能不
3、能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地 ？他把这个问题称为周游世界问题。6济南大学离散数学引例 3 四色问题 (Four Color Problem) 1852, Francis Guthrie（ 格色里） , 注意到 英格兰地图可以用 4种颜色染色 , 使得相邻面 (有一段公共边界 ,不只是有一个公共点 )有不同颜色 ; 他问其弟 Frederick 是否 任意 地图都有此性质 ?7济南大学离散数学韦尔奇 .鲍威尔法n v1 v2 v3v4v5v6v7 v88济南大学离散数学知识点：n 图的基本概念n 点与边的关联、点（边）相邻n 完全图、补图，子图、生成子图n 点度数n 握手定理n 图的同构7-1 图的基本概念9济南大学离散数学一、图的基本概念n 现实世界中许多现象能用某种图形表示 ,这种图形是由一些点和一些连接两点间的连线所组成。n 例： A、 B、 C、 D四个队举行篮球比赛， 为了表示个队之间比赛的情况， 我们作出下图。 在图中个小圆圈分别表示这个篮球队， 称之为结点。 如果两队进行过比赛， 则在表示该队的两个结点之间用一条线连接起来， 称之为边。 这样利用一个图形使各队之间的比赛情况一目了然。AB DC10
