《圖論在單詞接龍中的應(yīng)用.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖論在“單詞接龍”中的應(yīng)用計(jì)科0943白雪090600304125圖論知識(shí)：定義：通過圖G的每條邊一次且僅一次的回路稱為歐拉回路。存在歐拉回路的圖,稱為歐拉圖。定理1：無向連通圖G是歐拉圖G不含奇數(shù)度的結(jié)點(diǎn)(即G的所有結(jié)點(diǎn)的度均為偶數(shù))。定理2：一個(gè)連通(弱連通:如果不考慮有向圖中邊的方向所得到的無向圖是連通圖，則有向圖稱為弱連通圖。)有向圖具有歐拉回路的充要條件是G的每一個(gè)結(jié)點(diǎn)的入度和出度相等。具有歐拉通路的充要條件是除起點(diǎn)和終點(diǎn)外,每個(gè)結(jié)點(diǎn)的入度等于出度。對(duì)于起點(diǎn)，其出度比入度多1,對(duì)于終點(diǎn)，其出度比入度少1。

2、圖論在單詞接龍中的應(yīng)用假設(shè)有許多張卡片,每張卡片上都寫著一個(gè)英文單詞,現(xiàn)在要把這些卡片按照一定的順序連成串。這個(gè)順序要求每張卡片(第一張卡片可以除外)上的單詞的首字母恰好是前一張卡片上的單詞的尾字母,并且要求每張卡片只能用一次,簡(jiǎn)單地說就是“單詞接龍”。有一些單詞組通過適當(dāng)?shù)慕M合是可以完成接龍的,例“teach”,“teeth”,“yet”,“happy“但是某些單詞組卻不具備這樣的性質(zhì),比如“ok”,“old”,“deep”,“king”。問題的關(guān)鍵是能否找出一種科學(xué)的方法快速、準(zhǔn)確地判斷一組單詞是否可以按照上述

3、規(guī)則完成接龍呢?可以運(yùn)用圖論中的歐拉定理建立了數(shù)學(xué)模型,來求解該問題。對(duì)任意一組單詞,可以判斷出它們能否完成接龍。模型建立：假設(shè)不區(qū)分字母的大小寫,可以把所有的英文字母看成是26個(gè)節(jié)點(diǎn),把每一個(gè)單詞看作是一條有向邊,即弧。這樣,弧頭就是單詞的首字母,弧尾就是單詞的尾字母,且弧頭、弧尾必然都在A~Z這26個(gè)點(diǎn)當(dāng)中。一組單詞就可以構(gòu)成一個(gè)節(jié)點(diǎn)數(shù)有限的有向圖,模型建立起來了,而判斷單詞能否完成接龍的問題也就轉(zhuǎn)化成了一個(gè)圖論問題,即判斷一個(gè)有向圖中是否存在歐拉回路或者歐拉通路。（若能一筆把這些單詞連起來,則所有單詞構(gòu)成的有

4、向圖中最少存在著一條歐拉通路。當(dāng)然,也可能是歐拉回路。）例1：“teeth”,“teach”,“happy”,“yet”這4個(gè)單詞可以完成接龍,即teeth—happy—yet—teach,它們構(gòu)成的有向圖如圖1所示。圖1圖1中T點(diǎn)的入度為2,出度為1,出入度相差為1;H點(diǎn)的出度為2,入度為1,出入度相差為1;Y點(diǎn)的入度為1,出度為1,出入度相等。因此,圖1是滿足定理2的“除兩個(gè)結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)的入度等于出度。對(duì)于這兩個(gè)結(jié)點(diǎn),一個(gè)結(jié)點(diǎn)的出度比入度多1,另一個(gè)結(jié)點(diǎn)的出度比入度少1”這個(gè)充要條件的,故存在歐拉通路,可以

5、完成接龍。例2：“old”,“ok”,“king”,“deep”這4個(gè)單詞無法完成接龍,它們構(gòu)成的有向圖如圖2所示。圖2圖2中沒有回路,且O點(diǎn)的入度為2,出度為0,出入度之差為2,因此不可能有歐拉路,故不能完成接龍。由于圖的點(diǎn)數(shù)最多為26個(gè),若經(jīng)過合理地設(shè)計(jì),算法的復(fù)雜度可降到常數(shù)級(jí)。可以對(duì)定理做一個(gè)簡(jiǎn)單地應(yīng)用。圖論的正確應(yīng)用大大降低了單詞接龍求解的復(fù)雜度。謝謝！