《图论在单词接龙中的应用.ppt》由会员分享，可在线阅读，更多相关《图论在单词接龙中的应用.ppt（8页珍藏版）》请在金锄头文库上搜索。
1、图论在图论在“单词接龙单词接龙”中的应用中的应用 计科0943 白雪 090600304125图论知识：图论知识：定义：通过图定义：通过图G的每条边一次且仅一次的回路称的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图为欧拉回路。存在欧拉回路的图,称为欧拉图。称为欧拉图。定理定理1：无向连通图：无向连通图G是欧拉图是欧拉图G不含奇数度的结不含奇数度的结点点(即即G的所有结点的度均为偶数的所有结点的度均为偶数)。定理定理2：一个连通：一个连通(弱连通弱连通: 如果不考虑有向图中如果不考虑有向图中边的方向所得到的无向图是连通图，则有向图称边的方向所得到的无向图是连通图，则有向图称为弱连通图。
2、为弱连通图。)有向图具有欧拉回路的充要条件是有向图具有欧拉回路的充要条件是G的每一个结点的入度和出度相等。具有欧拉通的每一个结点的入度和出度相等。具有欧拉通路的充要条件是除起点和终点外路的充要条件是除起点和终点外,每个结点的入度每个结点的入度等于出度。对于起点，其出度比入度多等于出度。对于起点，其出度比入度多1,对于终对于终点，其出度比入度少点，其出度比入度少1。图论在单词接龙中的应用图论在单词接龙中的应用 假设有许多张卡片假设有许多张卡片, ,每张卡片上都写着一个英文单词每张卡片上都写着一个英文单词, ,现现在要把这些卡片按照一定的顺序连成串。这个顺序要求每张在要把这些卡片按照一定的顺序连成
3、串。这个顺序要求每张卡片卡片( (第一张卡片可以除外第一张卡片可以除外) )上的单词的首字母恰好是前一张上的单词的首字母恰好是前一张卡片上的单词的尾字母卡片上的单词的尾字母, ,并且要求每张卡片只能用一次并且要求每张卡片只能用一次, ,简单简单地说就是地说就是“单词接龙单词接龙”。有一些单词组通过适当的组合是可有一些单词组通过适当的组合是可以完成接龙的以完成接龙的, ,例例“teachteach”, ,“teethteeth”, ,“yetyet”, ,“happyhappy“但是某些单词但是某些单词组却不具备这样的性质组却不具备这样的性质, ,比如比如“okok”, ,“oldold”, ,
4、“deepdeep”, ,“kingking”。问题的关键是能否找。问题的关键是能否找出一种科学的方法快速、准确地判断一组单词是否可以按照出一种科学的方法快速、准确地判断一组单词是否可以按照上述规则完成接龙呢上述规则完成接龙呢? ?可以运用图论中的欧拉定理建立了数学可以运用图论中的欧拉定理建立了数学模型模型, ,来求解该问题。对任意一组单词来求解该问题。对任意一组单词, ,可以判断出它们能否可以判断出它们能否完成接龙。完成接龙。模型建立：模型建立：假设不区分字母的大小写假设不区分字母的大小写,可以把所有的英文字母可以把所有的英文字母看成是看成是26个节点个节点,把每一个单词看作是一条把每一个单
5、词看作是一条有向边有向边,即弧。这样即弧。这样,弧头就是单词的首字母弧头就是单词的首字母,弧尾就是单弧尾就是单词的尾字母词的尾字母,且弧头、弧尾必然都在且弧头、弧尾必然都在AZ这这26个点个点当中。一组单词就可以构成一个节点数有限的有当中。一组单词就可以构成一个节点数有限的有向图向图,模型建立起来了模型建立起来了,而判断单词能否完成接龙而判断单词能否完成接龙的问题也就转化成了一个图论问题的问题也就转化成了一个图论问题,即判断一个有即判断一个有向图中是否存在欧拉回路或者欧拉通路向图中是否存在欧拉回路或者欧拉通路。（若能若能一笔把这些单词连起来一笔把这些单词连起来,则所有单词构成的有向图则所有单词
6、构成的有向图中最少存在着一条欧拉通路。当然中最少存在着一条欧拉通路。当然,也可能是欧拉也可能是欧拉回路。回路。）例例1：“teeth”,“teach”,“happy”,“yet”这这4个单词可以个单词可以完成完成 接接 龙龙,即即teethhappyyetteach,它们构成的有向它们构成的有向 图如图图如图1所示。所示。 图图1图图1中中T点的入度为点的入度为2,出度为出度为1,出入度相差为出入度相差为1; H点的出度为点的出度为2,入度为入度为1,出入度相差为出入度相差为1;Y点的点的入度为入度为1,出度为出度为1,出入度相等。因此出入度相等。因此,图图1是满是满足定理足定理2的的“除两个
7、结点外除两个结点外,每个结点的入度等每个结点的入度等于出度。对于这两个结点于出度。对于这两个结点,一个结点的出度比一个结点的出度比入度多入度多1,另一个结点的出度比入度少另一个结点的出度比入度少1”这个这个充要条件的充要条件的,故存在欧拉通路故存在欧拉通路,可以完成接龙。可以完成接龙。 例例2：“old”,“ok”,“king”,“deep”这这4个单词无法完个单词无法完成成 接龙接龙,它们构成的有向图如图它们构成的有向图如图2所示。所示。 图图2 图图2中没有回路中没有回路,且且O点点 的入度为的入度为2,出度为出度为0,出入出入 度之差为度之差为2,因此不可能因此不可能 有欧拉路有欧拉路,故不能完成接故不能完成接 龙。龙。 由于图的点数最多为由于图的点数最多为26个个,若经过合理地设计若经过合理地设计,算算法的复杂度可降到常数级。可以对定理做一个简法的复杂度可降到常数级。可以对定理做一个简单地应用。单地应用。 图论的正确应用大大降低了单词接龙求解图论的正确应用大大降低了单词接龙求解的复杂度。的复杂度。 谢谢！
