图论在单词接龙中的应用.ppt_第1页
图论在单词接龙中的应用.ppt_第2页
图论在单词接龙中的应用.ppt_第3页
图论在单词接龙中的应用.ppt_第4页
图论在单词接龙中的应用.ppt_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

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

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

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个,若经

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论