歐拉圖及哈密頓ppt課件(編輯修改稿)
2025-06-08 08:41 本頁面
【文章內(nèi)容簡介】 設(shè) b與 u相鄰 ,此時 v與 b和 u都不相鄰 , 顯然與已知矛盾 ,因此 d(u)+d(v)n1,即 d(u)+d(v)?n 綜上所述 ,對 ?u,v?V(G),都有 d(u)+d(v)≥n, 因此 G中存在一條哈密頓回路 ,從而這 n個人能站成一圈 ,使得每一個人的兩旁站著自己認(rèn)識的人 . 第三節(jié) 并行運(yùn)算圖論模型與格雷碼 串行計算機(jī) :傳統(tǒng)的計算機(jī)一般稱為串行計算機(jī) ,即執(zhí)行程序是一次完成一個操作 .實際上 ,為解決問題而寫的算法都設(shè)計成一次執(zhí)行一步 ,這樣的算法稱為串行的 .到目前為止 ,幾乎所有書本描述的算法都是串行的 . 然而在有些問題上 ,如氣象模擬 ,醫(yī)學(xué)圖像及密碼分析等許多高強(qiáng)度計算問題 ,即使在超計算機(jī)上 ,也不能通過串行操作在合理時間范圍內(nèi)解決 。而且對計算機(jī)的運(yùn)行速度來講 ,還 存在著物理上的限制 ,即總有問題不能用串行操作在合理長度的時間之內(nèi)解決 .另外 ,隨著硬件價格的下降 ,使得制造并行計算機(jī)成為可能 . 并行計算機(jī)就是使用多個處理器實現(xiàn)在同一時間執(zhí)行多條指令 . 并行算法就是把問題分成可同時解決的若干子問題 ,其單個指令流控制著算法的執(zhí)行 ,包括把子問題送到不同的處理器 ,以及把子問題的輸入和輸出定向到適當(dāng)?shù)奶幚砥?. 采用并行處理 ,一個處理器需要另一個處理器產(chǎn)生的輸出 .因此 .處理器需要互聯(lián) .用圖來描述帶有多重處理器的計算機(jī)里處理器的互聯(lián)網(wǎng)絡(luò) ,是一種十分便利的方法 ,即所謂的并行運(yùn)算圖論模型 .在第一章中介紹的 n維立方體 Qn中 ,有 2n(n0)個處理器 ,每個處理器有自己的內(nèi)存 ,在一個單位時間內(nèi) ,n維立方體中的每個處理器同時處理一條指令 ,然后與相鄰的處理器通信 .若一個處理器要與一個不相鄰的處理器通信 ,第一個處理器要發(fā)送一些信息 ,這包括路徑信息及接受者的最終目的地 .當(dāng)然這要花費數(shù)個時間段 . 許多計算機(jī)已經(jīng)根據(jù) n維立方體 Qn的模型制造和運(yùn)行 .下面將證明 n維立方體 Qn中存在哈密頓回路 ,為此先介紹格雷碼 .格雷碼是以弗蘭克 .格雷的名字命名的 ,在 20世紀(jì) 40年代 ,他為了把傳送數(shù)字信號過程中的錯誤的影響降到最低而發(fā)現(xiàn)的 .下面介紹格雷碼的有關(guān)定義和構(gòu)造定理 . ? 定義 1 n 階格雷碼是序列 s1,s2,?st,(t=2n), ? 其中每個 si是 n位二進(jìn)制串，滿足 ? （ 1）每個 n位二進(jìn)制串都出現(xiàn)在序列中； ? （ 2） si與 si+1只有一位不同； ? （ 3） st和 s1只有一位不同。 定理 1令 G1表示序列，由 Gn1根據(jù)以規(guī)則來定義 Gn: （ 1）令 表示序列 Gn1的逆序； （ 2）令 表示在序列 G的每個成員前加 0所得的序列； （ 3）令 表示在序列 的每個成員前加 1所得的序列； （ 4）令 G為由 后加上 組成的序列。 RnG 1?39。 1?nG39。39。 1?nG RnG 1?39。1?nG 39。39。 1?nG例 1從 G1開始構(gòu)造 G3。 G 1 0 1 1 0 00 01 11 10 G2 00 01 11 10 10 11 01 00 000 001 011 010 110 111 101 100 G3 000 001 011 010 110 111 101 100 RG139。1G39。39。1GRG239。2G39。39。2G推論 .對于每個正整數(shù) n?2， n維立方體都包含一個哈密頓回路。 0000 0001 1001 1000 0010 0011 1011 1010 0110 0111 1111 1110 0100 0101 1101 1100 例 2 證明任一個有限集合的全部子集可以這樣排列順序使任何相鄰的兩個子集僅相差一個元素 . 證明 :設(shè)此有限集為 A={a1,a2,… ,an},用長為n的二進(jìn)制數(shù)列對應(yīng)它的 2n個子集 :當(dāng)且僅當(dāng)子集中含有 A的第 i個元素時 ,數(shù)列的第二個數(shù)碼為 1,否則為 2n個數(shù)列為頂點 ,當(dāng)且僅當(dāng)數(shù)列僅一個同位數(shù)碼相異時 ,該兩頂點間連一邊 ,得到一個圖 G為 n維立方體 .而 n維立方體為哈密頓圖 .按照一條哈密頓回路的順序排列對應(yīng)子集即可 . 第四節(jié) 算法的時間復(fù)雜性 一個算法是有限指令的集合 有限性 :任何算法都會在有限條指令執(zhí)行完 后結(jié)束。 確定性 :算法的每一步有精確的定義。 輸入有零個或多個輸入，且輸入取自特定 的對象集合。 輸出 :有一個或多個輸出與輸入有某種特定關(guān)系。 唯一性 :每一步執(zhí)行后所得到的中間結(jié)果是唯一的，且僅依賴于輸入和先前步驟的結(jié)果 .。 通用性 :算法適用于一類輸入。 問題是要求回答的提問通常有幾個參數(shù)它們的值是特定的，取自定義域。 問題的描述 :是對參數(shù)進(jìn)行描述，指出其解是滿足什么性質(zhì)的命題。 實例 :給問題的全體參數(shù)都指定了確定的值便得到一個問題的實例。 A是問題 P的算法，若算法 A對問題 P的每個實例都給出正確答案。 問題 P算法可解，若存在一個算法解答問題P。 算法分析 是指通過分析得到算法所需的時間和空間的估計量。 算法的復(fù)雜度是指執(zhí)行算法所需的時間和空間的量。 定義 1令 f和 g為從整數(shù)集合或?qū)崝?shù)集合到實數(shù)集合的函數(shù)，如果存在常數(shù) c和 k，使得只要 x?k就有 ?f(x)? ?c?g(x)? 則稱 f(x)是 O(g(x))記為 f(x)=O(g(x))讀作 f(x)是 O(g(x)) 定理 1: 令 f(x)=an xn +an1 xn1 +… +a1 x+a0其中 a0 、 a1 、 … 、 an1 、 an為實數(shù)，則f(x)=O(xn) 定理 2 設(shè) f1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1