有向图和和无向图.ppt

高散数学 CH7图的基本概念 1无向图及有向图 图论的起源 图论是组合数学的 一个分支,它起源 于1736年欧拉的第 篇关于图论的论 文,这篇论文解决 了著名的“哥尼 斯堡七桥问题” ,从而使欧拉成为 图论的创始人。 哥尼斯堡七桥问题解决方式 ◆莱昂哈德·欧拉( Leonhard euler)在1735年圆满 地解决了这一问题,证明这种方法并不存在,也顺带 解决了一笔画问题。他在圣彼得堡科学院发表了图论 史上第一篇重要文献。欧拉把实际的抽象问题简化为 平面上的点与线组合,每一座桥视为一条线,桥所连 接的地区视为点。这样若从某点出发后最后再回到这 点,则这一点的线数必须是偶数。 图论的起源 欧拉最后给出任意一种河—桥图能否全部 走一次的判定法则。如果通奇数座桥的地 方不止两个,那么满足要求的路线便不存 在了。如果只有两个地方通奇数座桥,则 可从其中任何一地出发找到所要求的路线 。若没有一个地方通奇数座桥,则从任何 一地出发,所求的路线都能实现,他还说 明了怎样快速找到所要求的路线。 ●不少数学家都尝试去解析这个事例。而这 些解析,最后发展成为了数学中的图论 吹 拉 定义一个图,如果能够从一点出 发,经过每条边一次且仅一次再 回到起点,则称为欧拉图 欧拉在论文中给出并证明了判 断欧拉图的充分必要条件定理,并证 明了七桥图不是欧拉图。 从这个问题可以看出: 图:图用点代表各个事物,用边代 表各个事物间的二元关系。 所以,图是研究集合上的二元 关系的工具,是建立数学模型的 个重要手段。 2、一百多年以后 “七桥”问题以后,图论的研究停滯了 百多年,直到1847年,基尔霍夫用“树 ”图解决了电路理论中的求解联立方程 的问题,十年后凯莱用“树”图计算有 机化学中的问题。在这一时期流行着两 个著名的图论问题:哈密尔顿回路问题 和“四色猜想”问题。 3.哈密尔顿回路问題 1856年,英国数学家哈密尔顿设计了 个周游世界的游戏,他在一个正 十二面体的二十个顶点上标上二十 个著名城市的名字,要求游戏者从 个城市出发,经过每一个城市一 次且仅一次,然后回到出发点 哈密尔顿回路图 此路线称为:哈密尔顿回路 而此图称为:密尔顿图 4、“四色猜想”问题 人们在长期为地图(平面图)上色时发 现,最少只要四种颜色,就能使得 有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决, 直到一百多年后,在计算机出现以 后,于1976年用计算机算了1200多 小时,才证明了四色猜想问题