图论在单词接龙中的应用

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

1、图论在“单词接龙”中的应用计科0943白雪090600304125图论知识：定义：通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图,称为欧拉图。定理1：无向连通图G是欧拉图G不含奇数度的结点(即G的所有结点的度均为偶数)。定理2：一个连通(弱连通:如果不考虑有向图中边的方向所得到的无向图是连通图，则有向图称为弱连通图。)有向图具有欧拉回路的充要条件是G的每一个结点的入度和出度相等。具有欧拉通路的充要条件是除起点和终点外,每个结点的入度等于出度。对于起点，其出度比入度多1,对于终点，其出度比入度少1。图论在单词接龙中的应用假设有许多张卡片,每张卡片上都写着一个英文单词,

2、现在要把这些卡片按照一定的顺序连成串。这个顺序要求每张卡片(第一张卡片可以除外)上的单词的首字母恰好是前一张卡片上的单词的尾字母,并且要求每张卡片只能用一次,简单地说就是“单词接龙”。有一些单词组通过适当的组合是可以完成接龙的,例“teach”,“teeth”,“yet”,“happy“但是某些单词组却不具备这样的性质,比如“ok”,“old”,“deep”,“king”。问题的关键是能否找出一种科学的方法快速、准确地判断一组单词是否可以按照上述规则完成接龙呢?可以运用图论中的欧拉定理建立了数学模型,来求解该问题。对任意一组单词,可以判断出它们能否完成接龙。模型建立：假设不区分字母的

3、大小写,可以把所有的英文字母看成是26个节点,把每一个单词看作是一条有向边,即弧。这样,弧头就是单词的首字母,弧尾就是单词的尾字母,且弧头、弧尾必然都在A~Z这26个点当中。一组单词就可以构成一个节点数有限的有向图,模型建立起来了,而判断单词能否完成接龙的问题也就转化成了一个图论问题,即判断一个有向图中是否存在欧拉回路或者欧拉通路。（若能一笔把这些单词连起来,则所有单词构成的有向图中最少存在着一条欧拉通路。当然,也可能是欧拉回路。）例1：“teeth”,“teach”,“happy”,“yet”这4个单词可以完成接龙,即teeth—happy—yet—teach,它们构成的有向图如图

4、1所示。图1图1中T点的入度为2,出度为1,出入度相差为1;H点的出度为2,入度为1,出入度相差为1;Y点的入度为1,出度为1,出入度相等。因此,图1是满足定理2的“除两个结点外,每个结点的入度等于出度。对于这两个结点,一个结点的出度比入度多1,另一个结点的出度比入度少1”这个充要条件的,故存在欧拉通路,可以完成接龙。例2：“old”,“ok”,“king”,“deep”这4个单词无法完成接龙,它们构成的有向图如图2所示。图2图2中没有回路,且O点的入度为2,出度为0,出入度之差为2,因此不可能有欧拉路,故不能完成接龙。由于图的点数最多为26个,若经过合理地设计,算法的复杂度可降到常

5、数级。可以对定理做一个简单地应用。图论的正确应用大大降低了单词接龙求解的复杂度。谢谢！