图论在“单词接龙”中的应用计科0943白雪090600304125 图论知识： 定义：通过图G的每条边一次且仅一次的回路称 为欧拉回路。存在欧拉回路的图,称为欧拉图。 定理1：无向连通图G是欧拉图G不含奇数度的结 点(即G的所有结点的度均为偶数)。 定理2：一个连通(弱连通: 如果不考虑有向图中边 的方向所得到的无向图是连通图，则有向图称为 弱连通图。)有向图具有欧拉回路的充要条件是G 的每一个结点的入度和出度相等。具有欧拉通路 的充要条件是除起点和终点外,每个结点的入度等 于出度。对于起点，其出度比入度多1,对于终点 ，其出度比入度少1。图论在单词接龙中的应用 假设有许多张卡片,每张卡片上都写着一个英文单词,现 在要把这些卡片按照一定的顺序连成串。这个顺序要求每张 卡片(第一张卡片可以除外)上的单词的首字母恰好是前一张 卡片上的单词的尾字母,并且要求每张卡片只能用一次,简单 地说就是“单词接龙”。有一些单词组通过适当的组合是可 以完成接龙的,例 “teach”,“teeth”,“yet”,“happy“但是某些单词 组却不具备这样的性质,比如 “ok”,“old”,“deep”,“king”。问题的关键是能否找 出一种科学的方法快速、准确地判断一组单词是否可以按照 上述规则完成接龙呢?可以运用图论中的欧拉定理建立了数学 模型,来求解该问题。对任意一组单词,可以判断出它们能否 完成接龙。 模型建立： 假设不区分字母的大小写,可以把所有的英文字母 看成是26个节点,把每一个单词看作是一条有向边 ,即弧。这样,弧头就是单词的首字母,弧尾就是单 词的尾字母,且弧头、弧尾必然都在AZ这26个点 当中。一组单词就可以构成一个节点数有限的有 向图,模型建立起来了,而判断单词能否完成接龙的 问题也就转化成了一个图论问题,即判断一个有向 图中是否存在欧拉回路或者欧拉通路。（若能一 笔把这些单词连起来,则所有单词构成的有向图中 最少存在着一条欧拉通路。当然,也可能是欧拉回 路。）例1：“teeth”,“teach”,“happy”,“yet”这4个单词可以完成接 龙,即teethhappyyetteach,它们构成的有向图如图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个,若经过合理地设计,算法 的复杂度可降到常数级。可以对定理做一个简单 地应用。图论的正确应用大大降低了单词接龙求解 的复杂度。谢谢！