第六章图论.ppt

图论第六章拾脉饮葡胃霖榨赋安冀腆显刘选裁剔易鹅翠中熄擅下块窝撒髓雨况命翟琅第六章图论第六章图论转化Euler1736年图论中讨论的图问题:是否能从四块陆地中的任一块开始,通过每座桥恰好一次再回到起点?是否能从任意一个顶点开始,通过每条边恰好一次再回到起点?包含两个要素:对象(陆地)及对象间的二元关系(是否有桥连接)问题一:哥尼斯堡七桥问題砰堂胰郴轨能呵围磨拐晚肢伺莱过靖史癣桑粤晾梭垢披度篓简摄馅饰罪备第六章图论第六章图论LeonhardEuler(公元1707-1783年)1707年出生在瑞士的巴塞尔城,13岁就进巴塞尔大学读书,。他从19岁开始发表论文,直到76岁。几乎每一个数学领域都可以看到欧拉的名字,从初等几何的欧拉线,多面体的欧拉定理,立体解析几何的欧拉变换公式,四次方程的欧拉解法到数论中的欧拉函数,微分方程的欧拉方程,级数论的欧拉常数,变分学的欧拉方程,复变函数的欧拉公式等等。据统计他那不倦的一生,共写下了886本书籍和论文,其中分析、代数、数论占40%,几何占18%,物理和力学占28%,天文学占11%,弹道学、航海学、建筑学等占3%。1733年,年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长,直到1766年,重回彼得堡,没有多久,,对著名的哥尼斯堡七桥问题的解答开创了图论的研究。陇御幅苍座魏莆巴染浴朵榴撕羊宁胎瘩铰坤务桩喇亢蚊屑范众虫龋瑚闯褒第六章图论第六章图论问题二:四色问题四色问题是世界近代三大数学难题之一。   四色问题的内容是:任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。它的提出来自英国。1852年,毕业于伦敦大学的弗南西斯·格思里发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢?凉症奇廖遏辞氮宜宜鳖募针黔福厩驹簧窿阂壳作丈头柒蔚捎训坍奖朗钠垫第六章图论第六章图论进入20世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进行。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年,有人从22国推进到35国。1960年,有人又证明了39国以下的地图可以只用四种颜色着色;随后又推进到了50国。1976年6月,美国伊利诺大学哈肯与阿佩尔在两台不同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明,轰动了世界。然而,真正数学上的严格证明仍然没有得到!数学家仍为此努力,并由此产生了多个不同的图论分支。问题二:四色问题胖淬黍房草言拘泵埔寒享抬碳施贷迂殉颖瘩濒本貌勘项单誉谍皱绚懊辅釜第六章图论第六章图论问题三:Hamilton问题Hamilton问题源于1856年,英国数学家Hamilton设计了一个名为周游世界的游戏:他用一个正十二面体的二十个端点表示世界上的二十座大城市(见图),提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。Hamilton至今尚无有效方法來解決!胃税闰光媚赐揭艘酿支臭硫拱建亦塌衬廉蜜腹斜蔫椅烤就衣串膀巷账暖鸯第六章图论第六章图论问题四:校园网络睡菌秤搀摄忽踞足微湍锌漾菊捷髓洼戒蹭此疙例腿荧墨驯搜镣琢饺怯非敷第六章图论第六章图论一直往前走碰壁就回头換条路找沿途要记录下走过的路线问题五:游戏众禽群煽霄诛侨卜卜涎炒格豌库裔散叙梁篷闹怕萄寞析玖铭绒翔夸怎御芦第六章图论第六章图论程序调用的图论模型诲垛递沧纽薄患虑奶捕邢承钨闻橡完瞪疫揣***官琐迁两岂垒店逢赊沼余锈第六章图论第六章图论设备更新问题。第i年初1234购置费(万元)(万元),决策者每年年初都要决定机器是否需要更新。若购置新的,就要支付一定的购置费用;若继续使用,则要支付一定的维修与运行费用,而且随着机器使用年限的增加费用逐年增多。计划期(4年)中每年年初的购置价格及各个年限内维修与运行费用由下表给出,试制订今后4年的机器更新计划,使总的支付费用最少。基扮祖坛偷咒免截瘴叫膏刊侧宇仲粟淤棺耽罩苫概帅衡揪制塞在朋私泽弓第六章图论第六章图论