《MPA定量分析方法》.pptVIP

杨健 中国人民大学 Renmin University of China 主讲人简介 杨健（英国兰卡斯特大学管理科学博士） 中国人民大学 公共管理学院MPA定量分析首席教授 公共管理定量分析研究所所长 电子政务博士生导师 金融信息中心主任 《投资与证券》主编 英国运筹学JORS国际顾问 国家高技术研究发展计划（863）评审专家 国家自然科学基金管理科学评审专家 企业年金投资管理机构评审专家 回头路 传言一：邓小平在一个地方视察，视察完毕后，人们安排他原路返回，邓小平发现回去的道路和来时一样很生气，令车停住，说，我一生从来不走回头路。 传言二：协兴街的老人说，小平属龙，他是从广安经渠江到嘉陵江再到长江进入大海，龙归大海不回头，所以他不回家。 Graph Theory 图论是一门很有实用价值的学科，它在自然科学、社会科学等各领域方面均有很大应用，近年来它发展迅速，应用广泛，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学、运筹学以及数学的其它分支中，在工程和交通运输中均获得了重要应用。 起源 图论也是一门起源于游戏的学科，它起源于欧拉关于哥尼斯堡七桥问题的研究。哥尼斯堡是东普鲁士首府，普莱格尔河横贯其中，上有七座桥将河中的两个岛和河岸连接，一个散步者怎样才能走遍七座桥而每座桥只经过一次？ 哥尼斯堡七桥问题（Konigsberg） 18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)有一条名叫普莱格尔（Pregel）的河流横经其中，河上有7座桥，将河中的两个岛和河岸连结，如图1所示。 城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这个问题看起来似乎不难，但人们始终没有能找到答案。这就是七桥问题，一个著名的图论问题。 当欧拉（Euler）在1736年访问Konigsberg, Prussia (now Kaliningrad Russia)时，以深邃的洞察力很快证明了这样的走法不存在！欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。 Léonhard　Euler，1707～1783 瑞士人欧拉是18世纪最杰出的数学家之一，他不但在数学上做出了伟大贡献， 而且把数学成功地应用到了其他领域。欧拉一生著书颇丰，其中有许多成为数学中的经典。 由于长期大量的写作，加上生活条件不良，他1735年患眼疾竟致右眼失明，并且于1771年左眼也完全失明。但他凭着惊人的记忆力和心算能力，通过与助手们讨论以及直接口授等方式，又完成了大量的科学著作，直至生命的最后一刻。 1736年欧拉向圣彼得堡科学院提交了一篇论文，欧拉把这个问题的物理背景变换并简化为一种数学设计（称作图或网络）：即把每一块陆地用一个点来代替，将每一座桥用连接相应的两个点的一条线来代替，从而相当于得到一个图。欧拉证明了这个问题没有解。欧拉指出欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于“位置几何”（莱布尼茨描述拓扑学时首先使用的名称）。 欧拉还发现，不论什么形状的凸多面体，其顶点数v、棱数e、面数f之间总有 v-e+f=2这个关系。v-e+f被称为欧拉示性数，成为拓扑学的基础概念。 在数论中，欧拉首先引进了重要的欧拉函数φ(n)，用多种方法证明了费马小定理。以欧拉的名字命名的数学公式、定理等在数学书籍中随处可见。与此同时，他还在物理、天文、 建筑以至音乐、哲学方面取得了辉煌的成就。 欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。  欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。 除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。 图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。 哥尼斯堡七桥问题的解决远远超出了它的娱乐价值，由此提出的新思想则开辟了数学的一个新的领域—图论。 当然游戏娱乐对于图论的作用并没有到此为止，此后许多著名的数学游戏成为图论和拓扑学发展的催化剂和导引，如哈密尔顿问题（绕行世界问题）、四色猜想等。 “迷路的旅行推销员” 1857年，爱尔兰数学家哈密尔顿(Hamilton)制作了一个“环球周游”的数学玩具。他用一个正十二面体的