图与网络

章节摘录

　　1．图论方法与问题　　哥尼斯堡（Konigsberg）七桥问题　在哥尼斯堡城的普莱格尔（Pregel）河中有两个小岛。在河的两岸和小岛之间有七座桥，如图1—1所示。问题是能否从某地出发通过每一座桥恰好一次而回到出发地？很多人尝试过，都没有成功，但却没有人说明为什么不能成功。直到1736年欧拉用图论方法证明了这个问题是不可能的。他将该问题转化为图1—2中的图，问能否从一个顶点开始一笔画出这个图形而回到该顶点？由于这个图的顶点的度全为奇数，因此答案是否定的。在第3节将详细讨论有关这方面的问题。由于欧拉1736年在他的论文中解决了这个问题并得到了更一般性的结论，使他成为图论的创始人，他的论文被认为是图论方面的第一篇论文而闻名于世。　　现实生活中的许多问题都可以用一个图来表示。例如，用顶点表示城市，若两个城市之间有一条铁路相连，则在两个顶点之间连一条边，于是一个交通网络就可以用一个图来表示。同样地，用顶点表示电话，用边表示两个电话之间的线路，则通讯网络就可以用一个图来表示；用顶点表示人，若两个人认识，则在对应的顶点之间连一条边，一个图就表示一个人际关系的网络。类似地，化学中的分子结构、物理学中的电网络、计算机的联网等问题都可以用一个图来表示。将优化与决策中的实际问题用一个图来表示，通过研究图的性质并设计优化的算法来解决这些问题，这就是优化的图论方法。

内容概要

　　刘桂真，1944年生人，1968年大学毕业于山东大学数学系，1981年研究生毕业于山东大学数学系。1985年至1987年在加拿大SimonFraser大学访问两年。自1981年以来一直从事图论和组合优化等方面的研究工作，共发表论文160余篇，出版著作4部，其中《运筹学》获教育部科技进步二等奖。先后共承担教学项目2项，其中国家级教学研究项目1项，国家和省部级科研项目16项，其中承担国家自然科学基金重点项目2项，面上项目6项。并获教学奖6项，其中省部级4项，厅局级奖励2项；获科技进步奖11项，其中省部级7项，厅局级奖励4项。1996年至2002年期间曾先后6次赴香港4所大学进行合作研究。目前为山东大学数学与系统科学学院教授，国务院聘任的博士生导师，曾任该院第一任院长。曾是国家教委高等学校数学与力学教学指导委员会委员，中国图论研究会理事长。目前兼任威海分校数学系系主任，是山东省科学技术拔尖人才，校聘关键岗位人员。1993年起享受政府特殊津贴，曾是《数学进展》和《应用数学》编委会编委，全国高校理科高等数学研究会理事长，全国组合数学和图论研究会副理事长等。目前是国家自然科学基金、博士点基金、博士后基金、优秀博士论文等通讯评议专家，是数学国家教学奖、数学和力学国家自然科学奖评审专家，国家科技部重大项目咨询专家，863项目评审专家等。目前是国际学术刊物GraphsandCombinatorics的编委。由于在科研方面的成绩突出，被“美国数学评论”聘为评论员及美国数学会会员，分别被美国和英国剑桥国际名人传记中心认为是有突出贡献的科学家而载入“世界名人录”，“世界科技工程名人录”等。曾是全国第九、十届政协委员，民盟山东省委员会副主任委员。曾被评为全国先进教职工、山大三八红旗手和山大十大女杰。2006年被评为山东省教学名师，2007年被评为国家教学名师。　　获奖情况　　“图论与最优化问题研究”于1997年获山东省科技进步二等奖（第一位）　　“关于图的因子理论的研究”于1995年获国家教委科技进步二等奖（第一位，独立完成）　　“关于拟阵基图理论的研究”于1992年获山东省科技进步二等奖（第一位，独立完成）　　“关于图论和拟阵中的组合拓扑方法”的研究于1991年获国家教委科技进步三等奖（第三位）　　关于拟阵理论的研究于1991年获山东省教委科技进步论文一等奖（第一位）　　1989，1990，1992年分别获山东省教委科技进步论文二等奖各一项（第一位）　　“运筹学”获1999年国家教育部教材科技进步二等奖（第一位）　　“运筹学课程的改革与实践”获2001年山东省优秀教学成果二等奖（第二位）　　图的正交因子分解和哈密尔顿圈问题研究，获2001年山东省科技进步三等奖（第一位）。

书籍目录

前言1．图论方法与问题2．最小连接问题3．最优路线问题4．图的匹配问题5．图的染色6．有向图7．网络流8．图的标号问题9．图论方法应用实例参考文献

作者简介

《图与网络:优化决策的图论方法》主要阐述网络最优化问题中运用的一些重要的图论方法和用图论方法解决的实际问题，如最小连接问题、最优线路问题、工作分派问题、网络流问题，以及图的染色和标号在实际中的应用等。书中附有大量的例子说明图论在自然科学和社会科学中的应用。

图书封面

---

 图与网络下载

---