图论简介.pptVIP

图 论Graph Theory 福州大学数计学院/软件学院 常安 ２011年3月 Welcome you to attend the lecture! Enjoy graph theory together! The Best and Worst JobsThe Best1. Mathematician2. Actuary3. Statistician4. Biologist5. Software Engineer6. Computer Systems Analyst7. Historian8. Sociologist9. Industrial Designer10. Accountant11. Economist12. Philosopher13. Physicist14. Parole Officer15. Meteorologist16. Medical Laboratory Technician17. Paralegal Assistant18. Computer Programmer19. Motion Picture Editor20. Astronomer “为了让所有学生，而不仅仅只是少数学生或那些幸运地能进入某类学校的学生，都能接受卓越的数学和科学教育，实现更高水平的数学和科学学习，美国必须全民动员起来。在未来的几十年中，年轻人将依赖于从今天的数学和科学教育中获得的技术和知识来分析问题、提出方案，将创造性的想法付诸实际。国家在经济发展中的创新能力、美国劳动力在全球经济中充满生机和活力的能力均依赖于宽厚的数学和科学学习基础。”这是美国必威体育精装版发布的报告《教育机会：改革公民数学和科学教育与全球经济》所强调的。据新出版的美国《科学》杂志报道，近日，纽约卡耐基基金会在美国首都华盛顿特区召开新闻发布会，发布卡内基―普林斯顿高等研究中心高级研究委员会的这份关于数学和科学教育的新报告。委员会主席、普林斯顿高等研究中心前主任、数学教授菲利普?格里菲斯作了主题演讲。 一份耗资150万美元的教育报告《科学》的文章指出，这是一项由卡内基基金会资助150万美元实施的研究项目。新报告综合了以前美国各州有关教育的绝望呼吁，并对目前美国在数学和科学教育方面的弱势提出严重警告；报告提出数学和科学教育应有更严格的内容、提高教学标准和评估水平、对教师进行更好的培训、建设创新能力更强的学校。格里菲斯认为，如果这些变革措施被采纳，那么不仅可以提高美国学生的数学和科学教育水平，而且还能让学校有所改变。新报告呼吁：思考全球化、行动区域化，全民动员起来，协作努力，提高美国的数学和科学教育水平。报告认为，美国正处于一个紧迫却又充满了机会的时刻：应尽快减少国家现有教育成果与未来所需求的教育体制间的差异，“世界发生了戏剧性的变化，我们的学校也应该适应这种戏剧性的变化”。 图论简介 简介内容 一. 图论的起源 二. 图的定义 三. 图论的应用 1.七座桥与一笔画问题 2.环游世界与Hamilton问题 3.广播频道与着色问题 4.药品存放与独立集问题 5.婚姻定理与匹配问题 6.电灯管道与覆盖集问题 7.信息流传与传播问题 8.网络与连通度问题 四. 结论 一. 图论的起源 二. 图的定义 三. 图论的应用 1.七座桥与一笔画问题 1.七座橋與一筆畫問題 2.环游世界与Hamilton问题 2.环游世界与Hamilton问题 3.广播频道与着色问题 3.广播频道与着色问题 图G的着色(Coloring) : 在每一點塗上一個顏色, 使得有邊相連的點必須塗不同色。 4.药品存放与独立集问题 4.药品存放与独立集问题 5.婚姻定理与匹配问题 5.婚姻定理与匹配问题 6.电灯管道与覆盖集问题 7.信息流传与传播问题 8.网络与连通度问题 8.网络与连通度问题 四. 结 论 * 教材 (Text Book) 　　任一图论教材 参考书目 (Reference) ? Graph theory with applications，J.A.Bondy, U.S.R.Murty，2008 ? Modern Graph Theory》，B.Bollobas，2000 ? 图论基础，魏暹荪编著 （陕西师范大学出版社，1990） 课程评分方法 (Grading Policies) ? 考试 　　第8次为考试时间，试题源自课堂例题或　　 作业　　 ? 听课出勤率 　　总计24课时，分8次完成！ 　　缺课达