图论在单词接龙中的应用

《图论在单词接龙中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2005年9月北京联合大学学报(自然科学版)Sep.2005第19卷第3期总61期JournalofBeijingUnionUniversity(NaturalSciences)Vol.19No.3SumNo.61图论在单词接龙中的应用孙君意(华中师范大学信息技术系,武汉430079)[摘要]讨论了“单词接龙”的求解问题。运用图论中的欧拉定理建立了数学模型,并且设计了比较优化的算法,编制了程序。对任意一组单词,该程序可以判断出它们能否完成接龙。经测试,该算法较之传统的穷举法明显地降低了复杂度。[关键词]

2、图论;欧拉路;单词接龙;图算法[中图分类号]O157.5[文献标识码]A[文章编号]1005-0310(2005)03-0030-04有这样一个古老的数学问题。假设有许多张图。卡片,每张卡片上都写着一个英文单词,现在要把2)定理1无向连通图G是欧拉图G不含这些卡片按照一定的顺序连成串。这个顺序要求奇数度的结点(即G的所有结点的度均为偶数)。每张卡片(第一张卡片可以除外)上的单词的首字3)定理2一个连通(弱连通)有向图具有欧母恰好是前一张卡片上的单词的尾字母,并且要求拉回路的充要条件是G的每一个结点的入度

3、和出每张卡片只能用一次,简单地说就是“单词接度相等。具有欧拉路的充要条件是除两个结点外,[1]龙”。有一些单词组通过适当的组合是可以完成每个结点的入度等于出度。对于这两个结点,一个接龙的,例如,“teach”,“teeth”,“yet”,“happy”。但是结点的出度比入度多1,另一个结点的出度比入度[2]某些单词组却不具备这样的性质,比如“ok”,“old”,少1。“deep”,“king”。问题的关键是能否找出一种科学运用这些定理,可以判断如图1所示的4个图的方法快速、准确地判断一组单词是否可以按照

4、上形中,右边的2个图形是可以一笔画出的,因为这2述规则完成接龙呢?笔者运用图论中的欧拉定理个图形分别存在着欧拉回路和欧拉路,而左边的2建立了数学模型,并且设计了比较优化的算法,编个图形则不行,因为它们不满足上述任何一条定理制了程序来求解该问题。对任意一组单词,该程序的条件。可以判断出它们能否完成接龙。1相关图论知识图论是离散数学的一个分支,它以图为研究对象,研究节点和边组成的图形的数学理论和方法。关于欧拉回路和欧拉路,简单地说欧拉回路要求边不能重复,结点可以重复。笔不离开纸,不重复地走完所有的边,回到原

5、处,就是所谓的一笔画。欧拉路与欧拉回路不同之处是它不要求回到原处。这些名字中的“欧拉”是因为欧拉解决了七桥问题,并发现了一笔画所需的性质。下面列出一些定义和定理:1)定义通过图G的每条边一次且仅一次的图1这4个图形可否一笔划出回路称为欧拉回路。存在欧拉回路的图,称为欧拉[收稿日期]2005-04-06[作者简介]孙君意(1984—),男,湖北十堰人,华中师范大学电子信息工程专业、华中科技大学计算机科学专业(双学位)在读学生,软件设计师,研究方向为数据通信与移动开发。第19卷第3期孙君意:图论在单词接龙中

6、的应用312数学模型的建立对于单词接龙的求解,最易想出的方法莫过于穷举法,在这些单词的全排列中若能找出一组满足接龙条件的组合即有解。然而,如果用穷举法,N个单词全排列共有N!种情况,算法复杂度O图3无欧拉路的有向图(N!),显然穷举法是行不通的。笔者的思路是建立这样一个数学模型,假设不区分字母的大小写,可以把所有的英文字母看成是26个节点,把每一3总体算法设计个单词看作是一条有向边,即弧。这样,弧头就是对于较少的单词可以通过人工画图,然后进行单词的首字母,弧尾就是单词的尾字母,且弧头、弧观察和计算,从而

7、得出结论。但是如果有上千单尾必然都在A～Z这26个点当中。一组单词就可词,人的大脑必然难以承受其复杂度。因此,必须以构成一个节点数有限的有向图,模型建立起来借助计算机。我们可以把解题的数学思想设计成了,而判断单词能否完成接龙的问题也就转化成了算法,按照算法编出程序,并把待测试的单词组放一个图论问题,即判断一个有向图中是否存在欧拉在输入文件,程序运行后读入文件中的数据,并执回路或者欧拉路。而且由于图的点数最多为26行已经设计好的算法,然后输出结果到输出文件,个,若经过合理地设计,算法的复杂度可降到常数通过

8、分析输出文件就可以得出结论。因此,设计一级。个好的算法是至关重要的,不仅要完全反映出定可以对定理做一个简单地应用。“teeth”,理,而且要综合考虑时间复杂度和空间复杂度的问“teach”,“happy”,“yet”这4个单词可以完成接龙,题。首先要做的就是如何把定理转化为算法。因即teeth—happy—yet—teach,它们构成的有向图如为笔者建立的是有向图模型,而定理2又是针对有图2所示。“old”,“ok”,“king”,“dee