一種表示工具——圖布置實驗實驗十主要內容一個時間安排問題圖論的起源人、狼、羊、菜渡河問題好算法還是壞算法圖的矩陣表示方法返回7/21/2023圖論的起源：七橋問題7/21/2023

c

a

b

d

c

a

b

d

圖論的起源：七橋問題7/21/2023歐拉——圖論之父■定義：線圖（圖論的研究對象）■定理：一個線圖存在通過每邊正好一次回到出發點的路線的充要條件是：1）圖要是連通的2）與圖中每一頂點相連的邊必須是偶數條。于是得出結論：七橋問題無解。圖論的起源：七橋問題返回7/21/2023無向圖，一般用大寫字母G,H表示。一種表示工具——圖頂點邊dcab7/21/2023無向圖：G=(V,E)，頂點集：V；邊集：E。

e與頂點u,v相關聯。

u與v相鄰。

兩邊相鄰。

重邊

c

a

b

d

一種表示工具——圖7/21/2023兩種特殊圖：簡單圖

完全圖，記為Knb

d

c

a

b

d

c

a

一種表示工具——圖7/21/2023有向圖：V1V2V3V5V4想你能給出一個可用有向圖描述的實際例子嗎？一種表示工具——圖7/21/2023網絡這些數字可以代表距離，費用，可靠性或其他的相關參數。12345869157103一種表示工具——圖7/21/2023(G)和(G)分別表示圖G的頂點數和邊數在無向圖中，v的度數，記為d(v)；在有向圖中，v的出度，記為d+(v);v的入度，記為d-(v)。一種表示工具——圖返回7/21/2023一個時間安排問題學校要為一年級的研究生開設六門基礎數學課：統計(S)，數值分析(N)，圖論(G)，矩陣論(M)，隨機過程(R)和數理方程(P)。按培養計劃，注冊的學生必須選修其中的一門以上，你作為教務管理人員，要設法安排一個課表，使每個學生所選的課程，在時間上不會發生沖突。7/21/2023一個時間安排問題7/21/2023SNGRPM?完成上述表示課程沖突關系的線圖直觀、清晰地表達已知信息的方式一個時間安排問題返回7/21/2023人狼羊菜渡河問題擺渡人F狼W羊G菜C7/21/2023南岸狀態：16種，其中WG,GC,WGC，從而FC,FW,F為不允許狀態，FWGCFWGFWCFGCFGOCGWWC10個允許狀態：人狼羊菜渡河問題7/21/2023FWGCFWGFWCFGCFGOCGWWC尋求圖中從頂點“FWGC”到頂點“O”的最短路徑，這樣的路徑有幾條？求出最優的渡河方案。想語言描述時未顯示的關系躍然紙上人狼羊菜渡河問題7/21/2023FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河問題返回7/21/2023圖的矩陣表示方法鄰接矩陣關聯矩陣邊矩陣鄰接順序表返回7/21/2023v1v2v5v6v7v4v3abjkcghidfe鄰接矩陣7/21/2023

無向圖的鄰接矩陣：A=(aij)nn，其中無向圖的鄰接矩陣有何特點？由鄰接矩陣是否能作出原圖？想鄰接矩陣返回7/21/2023關聯矩陣v1v2v5v6v7v4v3abjkcghidfe7/21/2023

無向圖的關聯矩陣：M=(mij)nm,其中想無向圖的關聯矩陣有哪些特征？由關聯矩陣能否作出原圖？關聯矩陣返回7/21/2023邊矩陣v1v2v5v6v7v4v3abjkcghidfe返回7/21/2023好算法還是壞算法算法無效算法的時間復雜性分析什么是算法時間復雜度量級比較有效算法返回7/21/2023一個算法就是解決某一特定問題的方法，是一系列確定步驟，它必須在有限的時間內終止。表述一個算法一般有兩種方式（1）

步驟描述；（2）

框圖。什么是算法7/21/2023例：求兩個正整數m和n的最大公因子的Euclid算法什么是算法輸入：正整數m,n。輸出：m和n的最大公因子。1）求余數m除以n，令r為所得的余數(0r<n)。2)判斷r是否為0。若r=0，則算法終止；否則，轉3)。3)互換。置mn,nr,返回第一步返回7/21/2023用行列式的定義求一個20階行列式的值，即使是每秒1000萬次的計算機也要花大約15萬年的時間。算法無效7/21/2023好算法還是壞算法如何才能簡便地判斷一個算法的有效性呢？在什么情況下一個問題找不到有效算法來求出正確解？想返回7/21/2023算法的時間復雜度——從輸入數據到計算出結果所需要的時間，它是輸入長n（問題規模）的一個函數。

算法的時間復雜性分析7/21/2023時間復雜度例如，求n個數最大者的一個算法如下：max=-999999fori=1:nifnumber(i)>maxnmaxn=number(i)endend記T(n)=c1+c2n為這個算法的時間復雜度。通常記T(n)=O(n).7/21/2023好算法還是壞算法時間復雜度若存在正數C和n0，使當nn0時，一個算法的執行時間T(n)Cf(n)，則稱該算法花了f(n)階的時間，記為T(n)=O(f(n))。7/21/2023時間復雜度分別是O(1),O(n),O(n2)

。例：對下面三個簡單的程序段，求時間復雜度。1)x=x+12)fori=1:nx=x+1end3)fori=1:nforj=1:nx=x+1endend好算法還是壞算法7/21/2023典型算法的執行時間時間復雜度n2n32nn!計算時間1/64秒2秒274世紀5*2662世紀n=128時各典型算法的執行時間返回7/21/2023

有效算法或好算法：以多項式時間為限界的算法。指數時間算法或壞算法：任何多項式都不是其時間復雜度T(n)的上界的算法好算法還是壞算法7/21/2023典型算法的處理規模算法時間復雜度一小時能處理的實例規模提高速度210倍一小時能處理的實例規模A1nN11024N1A2n2N232N2A32nN3N3+10A48nN4N4+3.3返回7/21/2023（1）若0<L<,稱f1(n)與f2(n)同量級,記為O(f1(n))=O(f2(n));（2）若L=0,則稱f1(n)的量級比f2(n)低,記為O(f1(n))<O(f2(n))；（3）若L=,則稱f1(n)的量級比f2(n)高,記為O(f1(n))>O(f2(n))。時間復雜度函數的量級比較7/21/2023顯然：1，logn，n，n2，

n3，n3，

…2n，

n!量級是由低到高。時間復雜度函數的量級比較7/21/20231．無論計算機速度多么高，功能多么強，用指數時間算法不能解大型問題。2.算法的時間復雜度函數的量級越低，算法的效率越高（就大型問題而言）。注意返回7/21/2023提問與解