数学建模图论方法专题
数学建模 图论方法专题
图论的基本概念问题1：七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点？业D哥尼斯堡七桥示意图
A B C D 哥尼斯堡七桥示意图 问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而 回到出发点？ 图论的基本概念
图论的基本概念七桥问题模拟图：B欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地
七桥问题模拟图: A B D C 欧拉指出：如果每块陆地所连接的桥都是偶数座，则 从任一陆地出发，必能通过每座桥恰好一次而回到出 发地。 图论的基本概念
用图论思想求解以下各题例1、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法
用图论思想求解以下各题 例1、一摆渡人欲将一只狼，一头羊，一篮菜从 河西渡过河到河东，由于船小，一次只能带一物 过河，并且，狼与羊，羊与菜不能独处，给出渡 河方法
离散状态空间：用三维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)
向量 位置 (0,0,0) 初始状态，狼，羊，菜均在西岸 (1,0,0) 狼已过河，羊，菜在西岸 (0,1,0) 羊已过河，狼，菜在西岸 (0,0,1) 菜已过河，羊，狼在西岸 (1,1,0) 羊，狼已过河，菜在西岸 (0,1,1) 羊，菜已过河，狼在西岸 (1,0,1) 狼，菜已过河，羊在西岸 (1,1,1) 目标状态，狼，羊，菜都已过河 离散状态空间: 用三维0-1向量表示（狼，羊，菜）在西岸状态，（在西岸则分量取0，否则 取1） 列出所有可能的状态