第八章图的基本概念 >图论 >图是由一些顶点和连接这些顶点的一些边 所组成的离散结构
第八章 图的基本概念 图论 图是由一些顶点和连接这些顶点的一些边 所组成的离散结构
图论教学目的 >采用图论的成果和方法,培养思考问题与 解决问题的能力
图论教学目的 采用图论的成果和方法，培养思考问题与 解决问题的能力
>8.1引言 >8.2路与回路 >8.3欧拉图 84哈密顿图 >8.5最短路 >86图论模型和证明
8.1 引言 8.2 路与回路 8.3 欧拉图 8.4 哈密顿图 8.5 最短路 8.6 图论模型和证明
>有关图论的提高参考书: > Bela bollobas. Modern graph Theory(现代 图论)科学出版社& Springer.2001
有关图论的提高参考书： Bela Bollobas. Modern Graph Theory (现代 图论). 科学出版社 & Springer. 2001
8.1引言 图论的起源与发展 二有向图 无向图 >四顶点度数 >五同构概念 六子图
8.1 引言 一 图论的起源与发展 二 有向图 三 无向图 四 顶点度数 五 同构概念 六 子图
5.1引言 >一图论的起源与发展 1起源:哥尼斯堡七桥问题 能否从河岸或小岛出发,通过每一座桥,而且仅仅通 过一次回到原地
5.1 引言 一 图论的起源与发展 1 起源：哥尼斯堡七桥问题 能否从河岸或小岛出发，通过每一座桥，而且仅仅通 过一次回到原地。 A C B D
1736年:图论历史元年 >在1736年,年仅29岁的瑞士数学家欧拉 ( Euler)发表了图论的首篇论文—《哥 尼斯堡七桥问题无解》,所以人们普遍认 为欧拉是图论的创始人。 Euler指出,如果在B点出发,B点处有3座 桥,经过其中之一离开,有经过另一桥回 来,因为要求每桥恰过一次,所以不得不 经过第3座桥离开,则无法回来。处在其他 出发点的情形是相似的
1736年：图论历史元年 在1736年，年仅29岁的瑞士数学家欧拉 （Euler）发表了图论的首篇论文——《哥 尼斯堡七桥问题无解》，所以人们普遍认 为欧拉是图论的创始人。 Euler指出，如果在B点出发，B点处有3座 桥，经过其中之一离开，有经过另一桥回 来，因为要求每桥恰过一次，所以不得不 经过第3座桥离开，则无法回来。处在其他 出发点的情形是相似的
2图论的三个发展阶段 1736年到19世纪中叶,萌芽阶段;多数问 题围饶游戏展开 >19世纪中叶到1936年,作为一个数学分支的 形成;图论问题(如四色问题、哈密顿图)大量 出现,也出现了以图为工具解决问题的成果。 1936年,KOng总结了图论200年来的研究成果, 出版了图论的第一部专著《有限图与无限图理论》 1936年以后,计算机科学的发展为图论的发 展提供了计算工具;现代科学技术的发展需要借 助图论来描述和解决各类课题中的各种关系
2 图论的三个发展阶段 1736年到19世纪中叶，萌芽阶段；多数问 题围饶游戏展开 19世纪中叶到1936年，作为一个数学分支的 形成；图论问题（如四色问题、哈密顿图）大量 出现，也出现了以图为工具解决问题的成果。 1936年，Konig总结了图论200年来的研究成果， 出版了图论的第一部专著《有限图与无限图理论》 1936年以后，计算机科学的发展为图论的发 展提供了计算工具；现代科学技术的发展需要借 助图论来描述和解决各类课题中的各种关系
3图论发展的原因 >1图论提供了一个自然的结构,由此产生 的数学模型几乎适合于所有科学(自然科 学和社会科学)领域,只要这个领域研究 的主题是“对象”与“对象”之间的关系。 >2图论已形成自己的丰富词汇语言,能简 洁地表示出各个领域中“对象-关系”结构 复杂而又难懂的概念 3图论提供了大量智力挑战问题
3 图论发展的原因 1 图论提供了一个自然的结构，由此产生 的数学模型几乎适合于所有科学（自然科 学和社会科学）领域，只要这个领域研究 的主题是“对象”与“对象”之间的关系。 2 图论已形成自己的丰富词汇语言，能简 洁地表示出各个领域中“对象-关系”结构 复杂而又难懂的概念。 3 图论提供了大量智力挑战问题
5.1引言 >二有向图 >1)定义8.1(有向图) 设V是一个非空集,E是V上的二元关系, 称有序对(v,E为有向图,记为G=(VE或 G(v,E。V中元素称为顶点(或点),V称 顶点集。E是VxV的子集,E中的元素是有序 对,称为弧,E称为弧集。 二元组表示图:例分>图82
5.1 引言 二 有向图 1） 定义8.1(有向图) 设V是一个非空集，E是V上的二元关系， 称有序对(V, E)为有向图，记为G=(V, E)或 G(V, E)。V中元素称为顶点（或点），V称 顶点集。E是VV的子集，E中的元素是有序 对，称为弧，E称为弧集。 二元组表示图：例图8.2