电↓科越女学 r街y时Bectrele8 cad Tecaology af Chiaa /956 本次课内容 一、图论简介 二、图的定义及其相关概念 三、图的同构
本次课内容 一、图论简介 二、图的定义及其相关概念 三、图的同构
电↓科放女学 r街y时Bectrele8 ciad Tecaology af Chins /956 一、 图论简介 (一)、发展历史 1、起源一哥尼斯堡七桥问题(1736年解决) 食@ 七桥问题 18世纪东普鲁土的哥尼斯堡城，有一条河穿过，河 上有两个小岛，有七座桥把两个岛与河岸联系起来（如 下图)。有人提出一个问题：一个步行者怎样才能不重 复、不遗漏地一次走完 七座桥，最后回到出发 点。后来大数学家欧 B 拉把它转化成一个几 何问题（如右图） 一笔闻问题。 测试1：A能按要求完成行走；B不能按要求完成行走
一、图论简介 (一)、发展历史 1、起源——哥尼斯堡七桥问题(1736年解决) 测试1：A 能按要求完成行走; B 不能按要求完成行走
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /9568 2、缓慢发展一 十九世纪中叶到二十世纪中叶 (1)周游世界问题（哈密尔顿问题，1857年） 十二面体 Ba&圈
2、缓慢发展——十九世纪中叶到二十世纪中叶 (1)周游世界问题(哈密尔顿问题,1857年) 十二面体
电子科越女学 r街y时Bectrele8 cad Tecaology af Chiaa /956 (2)四色问题（地图染色问题，1852年，格斯里） 还有所谓的克希荷夫生成树问题，欧拉多面体问题，图的平面性问题 以及一些组合优化和运筹学等问题
(2)四色问题(地图染色问题,1852年，格斯里) 还有所谓的克希荷夫生成树问题，欧拉多面体问题，图的平面性问题 以及一些组合优化和运筹学等问题
电子科越女学 r街y时Bectrele8 cad Tecaology afCh /956 (3)第一本图论著作（哥尼【匈牙利】，1936年出版） 哥尼在这本书里，总结了当时所有的图论成果。书 名叫《有限图与无限图理论). 3、快速发展—二十世纪中叶至今 经过最近几十年的发展，形成了一门独立学科。其 典型分支包括：结构图论，代数图论，拓扑图论， 网络图论，随机图论和极值图论。 (二)、图论所属学科 图论属于应用数学的一个分支，是研究“点”与 “线”组成的“图形”问题的一门科学
(3)第一本图论著作(哥尼【匈牙利】，1936年出版) 哥尼在这本书里，总结了当时所有的图论成果。书 名叫《有限图与无限图理论). 3、快速发展——二十世纪中叶至今 经过最近几十年的发展，形成了一门独立学科。其 典型分支包括：结构图论，代数图论，拓扑图论， 网络图论，随机图论和极值图论 。 (二)、图论所属学科 图论属于应用数学的一个分支，是研究“点”与 “线”组成的“图形”问题的一门科学