利用有向图解答过河类问题泉州五中郭仲英362000摘要过河类.doc

利用有向图解答“过河”类问题 泉州五中 郭仲英 362000 摘要：“过河”类问题是全国青少年信息学奥林匹克联赛信息学奥林匹克联赛全国青少年信息学奥林匹克联赛联赛3×3的九个方格，将1~8这八个自然数填入方格中，给定一个初始状态，如下图左所示，其中空方格用数字0表示。允许空格周围相邻的数字移入空格，但每次只能移动1格。对于任意给定的一个目标状态（如下图右所示），为实现从初始状态到目标状态的转换至少需要移动数字的步数。 这类问题，可以用实验的方法去寻求解决的途径，但是在有限的考试作答时间内用实验的方法显然是不可取的。当然，如果选手具备相应的数学知识（矩阵运算），用数学方法解决也是可以的，但是，利用图论中有向图的概念去解决是较为直观的、简洁的。 二、图论的基本概念 在计算机科学中，数据是计算机程序加工处理的对象，抽象地说，数据是对客观事物所进行的描述。数据元素之间抽象化的相互关系称为数据的逻辑结构，这种相互关系可用一组运算及相应的运算规则来描述，简称为数据结构。图是一种复杂的数据结构。 图 G 由两个集合V( G )和E( G )所组成，记作G= (V, E)，其中V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。 例如，右边所示的图，其顶点集V＝｛a, b, c, d｝，边集E＝｛e1， e2， e3， e4， e5｝，其中e1＝(a,b)， e2＝(a,c)，e3＝(a,d)， e4＝(b,c)，e5＝(c,d)。 如果图中每条边都是顶点的无序对，则称此图为无向图。用(X, Y) 表示。(X, Y)表示顶点X和顶点Y之间的边。(X, Y)和（Y,X）是表示同一条边。 与无向图相应，如果图中每条边都是顶点的有序对，即每条边在图示时都用箭头表明了方向，则称此图为有向图。有向图中的边称为“弧”，用X,Y表示。X,Y表示从顶点X发出而到达顶点Y的一条弧，其中X为弧尾或初始点，Y为弧头或终端点。X,Y与Y,X表示不同的弧。 若（X，Y）是图中的一条边，则称顶点X和Y是邻接的，边（X，Y）依附于顶点X和Y。在无向图中，顶点的度是指依附于该顶点的边数。在有向图中，以某顶点为头，即终止于该顶点的弧的数目称为该顶点的入度，记为deg-(vi)。以某顶点为尾，即起始于该顶点的弧的数目称为该顶点的出度deg+(vi)。 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj，则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应是属于E的边。路径上边或弧的数目称为路径长度。vi 称为这条路径的起点，vj称为这条路径的终点。当Vi=Vj时，这条路径称为一个回路。对于一个有向图是一个通路或一个回路，则必满足 (1)与之相对应的无向图是连通的； (2)满足| deg+(vi)－deg-(vi)|=1的顶点个数为2或0，并且其余的顶点均满足deg+(vi)=deg-(vi)=1。 三、利用图论知识求解“过河”类问题 我们以“农夫、狼、羊、草”过河的问题为例，具体分析利用图论知识求解的过程。假设分别用M表示农夫，W表示狼，表示羊，表示草。16种：MWSG、MWS、MWG、MSG、WSG、MW、MS、MG、WS、WG、SG、M、W、S、G、φ，这里φ表示原岸是空集， 即人、狼、羊、草都已运到河的对岸去了。 根据题意可以得到，这16种情况中有6种情况是不允许出现的。它们是：WSG（狼、羊、草）、MW（农夫、狼）、MG（农夫、草）、WS（狼、羊）、 SG（羊、草）、M（农夫）。如MG表示人和干草在原岸，而狼和羊在对岸，这显然是不行的。因此，允许出现的情况只有10种。 我们构造一个图，它的顶点就是这10种状态。如果船某次从河的一岸划往另一岸时，使原岸的状态从V变成V’，我们就作一条从V到V’的弧，这样就可以得到如下图所示的有向图 由于船是在两岸间往返的，那么“过河”问题就转换成在上图中找出一条由结点MWSG到结点φ的路径，这条路径中相邻的两条弧或者都是由同一点引出的，或者都是进入同一个结点的，这样的路径是很容易找到的。从图中得到两条这样的路径，路径一：人狼羊草→狼草→人狼草→草→人羊草→羊→人羊→φ，路径二：人狼羊草→狼草→人狼草→狼→人狼羊→羊→人羊→φ，它们的长度都是7，也就是说，农夫至少要经过7次摆渡才能将狼、羊、草都安全摆渡到对岸，可以有两种方案。如果要求解至少需要摆渡的次数，那就是去找路径长度最小的路径。 对于油瓶分油问题，利用图论的知识用同样的方法可以得到解决，倒9次油可将10kg的油均分成两份。对于八数码问题中所示的原始状态和目标