离散数学图论部分市公开课一等奖省赛课获奖PPT课件.pptx

该【离散数学图论部分市公开课一等奖省赛课获奖PPT课件 】是由【liaoyumen】上传分享，文档一共【226】页，该文档可以免费在线阅读，需要了解更多关于【离散数学图论部分市公开课一等奖省赛课获奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四部分 图论
第1页
图论问题起源
18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们经过七座桥相互连接,:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”
S
N
A
B
第2页
陆地
岛屿 岛屿
陆地
哥尼斯堡七桥问题
怎样不重复地走完七桥后回到起点？
。
。 。
。
A
B
C
D
第3页
当初人们热衷于这么游戏：构想从任一个地方出发经过每座桥一次且仅一次后回到原地, 这是否可能?但屡次实践都发觉不行。
1727 年欧拉朋友向欧拉提出了这个问题是否有解？
1736 年欧拉用图论方法处理了这个问题,写了第一篇图论论文,成为图论创始人。
以后称此问题为哥尼斯堡七桥问题。
第4页
但在此之后100年间，没有大进展。
直到Kirchhoff(克希霍夫)用树理论处理了电网络问题。这些结果引发了人们重视,图论研究进入了一个发展时期。
直到1920年, 科尼格(Konig)撰写了许多图论方面论文。在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》, 总结了200年来图论研究主要结果。
今后50年, 图论经历了一场爆炸性发展, 成为数学科学中一门独立学科。
第5页
几十年来图论在理论上和应用上都得到很大 发展, 尤其是在近30多年来因为计算机广泛应用而又得到飞跃发展。
在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少结果，对计算机学科中操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛应用。
这里主要讨论图基本概念和算法, 为今后学习和研究打下基础。
第6页
本章首先给出图、简单图、完全图、子图、路和图同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵定义。最终介绍了欧拉图与哈密尔顿图。
第7页
图定义
第8页
第9页
例 画出以下图形。
G=<V,E>,其中V={v1,v2,v3,v4,v5},
E={(v1,v1), (v1,v2), (v2,v3), (v2,v3),
(v1,v5), (v2,v5), (v4,v5)}。
v1
v2
v3
v4
v5
e1
e2
e3
e4
e5
e6
第10页