数学建模 图论方法专题.

Presentation on theme: "数学建模 图论方法专题."— Presentation transcript:

1 数学建模 图论方法专题

2 图论的基本概念 问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而 回到出发点？ A B C D 哥尼斯堡七桥示意图

3 图论的基本概念 欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。 七桥问题模拟图: C B
A B D C 欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。

4 用图论思想求解以下各题 例1、一摆渡人欲将一只狼，一头羊，一篮菜从 河西渡过河到河东，由于船小，一次只能带一物 过河，并且，狼与羊，羊与菜不能独处，给出渡 河方法。

5 离散状态空间: 用三维0-1向量表示（狼，羊，菜）在西岸状态，（在西岸则分量取0，否则取1） 列出所有可能的状态 向量 位置 (0,0,0)
初始状态，狼，羊，菜均在西岸 (1,0,0) 狼已过河，羊，菜在西岸 (0,1,0) 羊已过河，狼，菜在西岸 (0,0,1) 菜已过河，羊，狼在西岸 (1,1,0) 羊，狼已过河，菜在西岸 (0,1,1) 羊，菜已过河，狼在西岸 (1,0,1) 狼，菜已过河，羊在西岸 (1,1,1) 目标状态，狼，羊，菜都已过河

6

7 被删的边 原因 (0,0,0)到(1,0,0) 羊吃菜 (0,0,0)到(0,0,1) 狼吃羊 (0,1,1)到(1,1,1)
问题：沿立方体的边寻找一条从 (0,0,0) 到 (1,1,1)的允许路径. 首先我们要删去一些引起某东西被吃的边。 被删的边 原因 (0,0,0)到(1,0,0) 羊吃菜 (0,0,0)到(0,0,1) 狼吃羊 (0,1,1)到(1,1,1) (1,1,0)到(1,1,1)

8

9 解答1 解答2

10 例2、考虑中国象棋的如下问题： （1）下过奇数盘棋的人数是偶数个。 （2）马有多少种跳法？ （3）马跳出后又跳回起点，证明马跳了偶数步。 （4）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？

11 立即疯 (Instant Insanity puzzle)
游戏道具：四个六个侧面上涂上四种不同的颜色的立方体，比如红，绿，蓝、白 注：正面均为白色 游戏目标：把四个正立方体叠成一个正立方棱柱，使棱柱的四个侧面都分别有四种颜色。

12 游戏难度 每个立方体有24种不同的放置方法。 四个正立方体叠成一个正立方棱柱，所有可能的叠放方式数为 4!× 24 4 =7962624
穷举所有可能来求解显然不可行， 会把你搞疯的。

13 游戏求解（图论模型） 每种颜色用一个顶点来表示 对于第i个立方体, 在相对面对应颜色的顶点连一条边， 并给予标号i.
如对应第1个立方体： 前=白, 后=蓝, 白色顶点，蓝色顶点间连一条标号为1的边； 左=红, 右=红, 红色顶点上加一条标号为1的环； 上=绿, 下=蓝, 绿色顶点，蓝色顶点间连一条标号为1的边。 1 立方体1的图论表示.

14 图论模型 4 2 3 3 立方体2 立方体3 立方体4

15 立即疯图论模型 由四个立方体的图论模型构造4个顶点，12条边的多重图. 1 3 4 2

16 图论模型 4 2 3 3 立方体2 立方体3 立方体4

17 立即疯图论模型 由四个立方体的图论模型构造4个顶点， 12条边的多重图. 1 3 4 2

18 游戏解的图论特征 假设四正立方体已按要求叠成一个正立方棱柱. 子图的特征: 画出多重图中和前后面相对应边的生成子图。
画出多重图中和左右面相对应边的生成子图。 子图的特征: 包含四个顶点. 包含分别来自四个不同立方体所对应图的四条边。 每条边只出现一次。 每个顶点的度数均为2.

19 一些子图 在前面的图中，可以找的如下三个边不交的子图. 1 4 2 3 3 4 1 2 1 4 3 2 A B C

20 一些子图 其中有两个子图满足要求. 一个用来表示左右侧面，另一个用来表示前后侧面。 接下来就可以按上面两图来叠放四个立方体. 左右侧面
3 4 1 2 接下来就可以按上面两图来叠放四个立方体.

21 实验1 如图为一个宝窟的示意图,它共分为16个房间,房间都是连通的,每一间地上都有数量不同的金块。
你可以从入口进去,但必须从出口出来,每到一间房内就捡起那里面的全部金块,不过每个房间只能进去一次.(图中假设左侧表示入口,右侧表示出口) 9 3 8 7 1 5 30 10 2 6 11 13 4 问题1：试问你最多可以捡到多 少块金块?并说明你的算法。 问题2：如果出入口位置发生改变，结果又将如何？