课件实验07图与网络.pdf

第八章 游戏1 人、狼、羊、草渡河。 一农夫, 带着一条狼, 一只羊和一捆草, 来到了河边。当他准备 渡河时才发现, 河边唯一的一条小船仅能承载他和另外一样东西。 然而他不能将狼和羊单独留河的一岸, 也不能将羊和草单独留河的 一岸, 但是他可以来回反复摆渡。 农夫应该如何摆渡, 才能以最少的摆渡次数成功渡河？ 应该构建一个怎样的模型来分析这一问题？ 游戏2 一笔画 有如下图形，是否能够采用笔不离纸连续一笔，不重复笔画的 将其画出？ 为什么画不出来呢？这就引出了一个古老的话题 ！ 引言 十八世纪的哥尼斯堡城中流过一条河 （普雷.格尔河），河上有 7 座桥连接着河的 和河中的两个小岛。当时那里的人们热衷于 这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原 出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走 法不存在，这就是著名的 “哥尼斯堡 7 桥”难题。 引言 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论 文给予了完满的解决，这是图论的第一篇 。 是怎样研究这个问题的呢? C B A D 引言 将 “哥尼斯堡 7 桥”抽象成：在如下的图形中，从A, B, C, D任一点出发，能否通过每条边 （连线）一次且仅一次，再回到 该点， 证明了该图不存在 （所谓的） “ 回路”，所以无解 ！ C B A D 引言 图论的第一篇 产生后的两百 图论的发展是缓慢的，直 到 1936 年匈牙利数学家 O.König写出了图论的第一本专著 《有限 图与无限图的理论》。 在图论的发展过程中还有两位著名科学家值得一提，他们是物 理学家 和化学家 ，他们在各自的专业领域的研究中应 用了图论的基本思想，也对图论的发展作出了重要贡献 ！ 引言 图论的历史上最具有 色彩的问题也许要数著名的 “四色 猜想”了——历史上许许多多数学猜想之一。它描述对一张地图着 色的问题，幸运的是在 1970’s 终于由 的两位数学家借助大型 计算机将其证明了。 图论与网络分析理论所研究的问题十分广泛，内容极其丰富。 正如一位数学家所说： “可以说，图论为任何一个包含了某种二元 关系的系统提供了一种分析和描述的模型。” 人、狼、羊、草渡河游戏—— 图的模型描述： M （Man），W （Wolf ），G （Goat），H （Hay）。 点—— v 表示河的一岸允许出现的状态； i u 河的另一岸允许出现的状态。 i 则有：v ，u = （M，W ，G，H）； v ，u = （M，W ，G）； 1 1 2 2 v ，u = （M，W ，H）； v ，u = （M，G，H）； 3 3 4