课程设置 图的基本概念 欧拉图与哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色 东南大学计算机科学与工程学院 同的出学 图论
图的基本概念 欧拉图与哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色
图论的由来七桥问题 ■世界上最多产的数学家 ■“分析的化身 ■除雅各比外无人企及的算 法大师 ■可在任何条件下工作终因 为过分劳累双目失明 ■因应用数学而备受各国政 府追捧 ■临死一刻仍保持科研风格 1707-1783 是否存在一条路线,可不重复地走遍七座桥。这就是哥尼斯堡七 A 桥问题1735年,有几名大学生写信给欧拉。欧拉在亲自观察了哥 尼斯堡七桥后,认真思考走法,但始终没能成功,于是他怀疑七 桥问题是不是原本就无解。1736年,在经过一年的研究之后,29 岁的欧拉提交了《哥尼斯堡七桥》的论文,圆满解决了这一问题, 同时开创了数学新一分支一一图论。 东南大学计算机科学与工程学院 同的出学 图论
世界上最多产的数学家 “分析的化身” 除雅各比外无人企及的算 法大师 可在任何条件下工作,终因 为过分劳累双目失明 因应用数学而备受各国政 府追捧 临死一刻仍保持科研风格 1707-1783 是否存在一条路线，可不重复地走遍七座桥。这就是哥尼斯堡七 桥问题. 1735年，有几名大学生写信给欧拉。欧拉在亲自观察了哥 尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七 桥问题是不是原本就无解。 1736年，在经过一年的研究之后，29 岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题， 同时开创了数学新一分支——图论
图论的由来—四色问题 1852年,一位英国大学生发现了一种有趣的现象:“看 来,每幅地图都可以用四种颜色着色,使得有共同边界 的国家都被着上不同的颜色。”这个现象能不能从数学 上加以严格证明呢?他和在大学读书的弟弟决心试一试。 兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠, 可是研究工作没有进展。 1852年10月23日,他的弟弟就这个问题的证明请教了他的老师、著名数学家德,摩根,摩根也没有 能找到解决这个问题的途径,于是写信向自己的好友、著名数学家汉密尔顿爵士请教。汉密尔顿 接到摩尔根的信后,对四色问题进行论证。但直到1865年汉密尔顿逝世为止,问题也没有能够解 决。自此之后百年,无人能解决该问题,因此成为世界三大数学猜想之 1976年,两位美国数学家在伊利诺伊大学的BM360机上分1482种情况检查,历时1200个小时,作 了100亿个判断,证明了四色定理。并分别与1989年和1998年修正了部分瑕疵之后,宣告彻底解决 该问题。 东南大学计算机科学与工程学院 同的出学 图论
1852年，一位英国大学生发现了一种有趣的现象：“看 来，每幅地图都可以用四种颜色着色，使得有共同边界 的国家都被着上不同的颜色。”这个现象能不能从数学 上加以严格证明呢？他和在大学读书的弟弟决心试一试。 兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠， 可是研究工作没有进展。 1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩根，摩根也没有 能找到解决这个问题的途径，于是写信向自己的好友、著名数学家汉密尔顿爵士请教。汉密尔顿 接到摩尔根的信后，对四色问题进行论证。但直到1865年汉密尔顿逝世为止，问题也没有能够解 决。自此之后百年，无人能解决该问题，因此成为世界三大数学猜想之一。 1976年，两位美国数学家在伊利诺伊大学的IBM360机上分1482种情况检查，历时1200个小时，作 了100亿个判断，证明了四色定理。并分别与1989年和1998年修正了部分瑕疵之后，宣告彻底解决 该问题
图论的由来路线选择问题 汉密尔铡周游世界问题 1859年,威廉·汉密尔顿爵士在给他朋友的一封信中,首先谈 到关于十二面体的一个数学游戏:能不能在图中找到一条回路 使它含有这个图的所有结点?他把每个结点看成一个城市,联 结两个结点的边看成是交通线。于是他的问题就是能不能找到 旅行路线,沿着交通线经过每个城市恰好一次,再回到原来的 出发地,他把这个问题称为周游世界问题。 中国邮递员问题 简单来说,邮递员问题就是在一个已知的地区,邮差要设法找到 条最短路径,可以走过此地区所有的街道,且最后要回到出发 点,中国邮递员问题由管梅谷教授在1960年提出,而美国国家标 准和技术研究院(NIST)的 Alan Go I dman首先将此问题命名为 · 中国邮路问题 东南大学计算机科学与工程学院 同的出学 图论
1859年，威廉·汉密尔顿爵士在给他朋友的一封信中，首先谈 到关于十二面体的一个数学游戏：能不能在图中找到一条回路， 使它含有这个图的所有结点？他把每个结点看成一个城市，联 结两个结点的边看成是交通线。于是他的问题就是能不能找到 旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的 出发地，他把这个问题称为周游世界问题。 简单来说，邮递员问题就是在一个已知的地区，邮差要设法找到 一条最短路径，可以走过此地区所有的街道，且最后要回到出发 点，中国邮递员问题由管梅谷教授在1960年提出，而美国国家标 准和技术研究院（NIST）的 Alan Goldman 首先将此问题命名为 中国邮路问题
第十四章图的基本概念 ●第一节:图 ●第二节:通路、回路、图的连通性 ●第三节:图的矩阵表示和运算 东南大学计算机科学与工程学院 图论 2024 同的出学
第十四章 图的基本概念 ⚫第一节：图 ⚫第二节：通路、回路、图的连通性 ⚫第三节：图的矩阵表示和运算 2021/2/2