图论在单词接龙中的应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图论在“单词接龙”中的应用,计科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个,若经过合理地设计,算法的复杂度可降到常数级。可以对定理做一个简单地应用。,图论的正确应用大大降低了单词接龙求解的复杂度。,谢谢！,