(2)b隨機地向a提問從s如何到達(dá)m1

1、隨機性在計算機領(lǐng)域中的作用,,隨機性的作用,“Randomization is a big idea in computer science.”---C. E. Leiserson @ MIT,隨機性的作用,賓夕法尼亞大學(xué)的André DeHon在“Big Ideas in Computer Science in Computer Science and Engineering”中總結(jié)了所有計算機學(xué)科中有代表性的重要思想，其

2、中多次提到了“隨機性”。,1. 隨機化的快速排序算法,,確定性的快速排序算法,確定性的快速排序算法的效率依賴于pivot值的選取。只要pivot值的選取方式固定，都存在一些規(guī)模為n的輸入，使得快速排序算法效率為Θ(n2)。例如，如果每次選取pivot值為待排序數(shù)組的最后一個值，則快速排序算法對于已經(jīng)排序好的數(shù)組效率最低。也就是說，確定性的快速排序算法希望輸入數(shù)據(jù)沒有任何規(guī)律，是完全隨機的。,隨機化的快速排序算法,每次在輸入數(shù)

3、據(jù)中隨機地選取pivot值。不存在任何輸入使得隨機化的快速排序算法在該輸入下復(fù)雜度一定為Θ(n2)。隨機化的快速排序算法不依賴于外部輸入數(shù)據(jù)的隨機性。,隨機算法的作用之一：降低對輸入數(shù)據(jù)隨機性的依賴,,,確定性的快速排序算法,依賴于輸入數(shù)據(jù)的“隨機性”,隨機性的快速排序算法：帶有一種內(nèi)置的隨機性(built-inrandomness),不依賴輸入數(shù)據(jù)的“隨機性”,,,2. 計算“平均成績”問題,,計算“平均成

4、績”問題,n個學(xué)生P1,P2,…,Pn參加了一次考試，學(xué)生Pi的成績?yōu)镃i(1≤i≤n)?，F(xiàn)在這n個學(xué)生要計算他們的平均成績，并且保證：(1) 任何一個學(xué)生都不泄露自己的成績。(2) 即使有k個學(xué)生之間相互共享信息，這k個學(xué)生最多也只能知道其余n-k個學(xué)生的平均成績。是否存在一種可行的方案？,協(xié)議(protocol),我們通過設(shè)計一個“協(xié)議”來解決這個問題。簡單地說，“協(xié)議”是兩個(或兩個以上)人為完成某項任務(wù)而進行的一

5、系列操作步驟。最簡單的協(xié)議是“切蛋糕”協(xié)議。參與者：兩個人A和B。任務(wù)：公平地分一塊蛋糕。操作步驟：(1)A把蛋糕切成2塊。 (2)B選走其中一塊蛋糕。 (3)A取走剩下的那塊蛋糕。,計算“平均成績”問題,參與者： n個學(xué)生P1,P2,…,Pn任務(wù)：計算平均成績(滿足前面提到的兩個條件)步驟：？,協(xié)議1,思想：假設(shè)考試包含n道題目。每個同學(xué)Pi負(fù)責(zé)統(tǒng)計所有同學(xué)第i道題目的得分。最后把所有同學(xué)的統(tǒng)計

6、結(jié)果加起來，得到總成績。,協(xié)議1,(1) 每個學(xué)生Pi把自己的成績分成n份Ci=Ci1+Ci2+…+Cin（其中Cij代表第i個同學(xué)第j道題的分?jǐn)?shù)），學(xué)生Pi把Cij告訴給學(xué)生Pj。(2) 每個學(xué)生Pj計算并公布Dj=C1j+C2j+…+Cnj (所有學(xué)生第j道題的得分)。(3) 計算D1+D2+…+Dn，得到總成績。,協(xié)議1的優(yōu)點,一方面，為了計算總成績，每個學(xué)生必須把自己的成績以某種方式發(fā)布出去，實現(xiàn)“信息共享”。另一方面，

7、任何學(xué)生都不能直接把自己的成績告訴給任何人。每個學(xué)生Pi把自己的成績分成n份，把其中n-1份分別告訴其他n-1個同學(xué)。這樣每個學(xué)生從Pi那得到的只不過是關(guān)于學(xué)生Pi成績的“部分信息”。,協(xié)議1的缺點,考試未必恰好包含n個考試題目。假設(shè)k個同學(xué)共享信息，可以大概估計其他同學(xué)的考試分?jǐn)?shù)。,協(xié)議2,(1) 每個學(xué)生Pi把自己的成績分成n份Ci=Ci1+Ci2+…+Cin(對任意j, Cij為0和Ci之間的隨機數(shù))，學(xué)生Pi把Cij告訴給

8、學(xué)生Pj。(2) 每個學(xué)生Pi計算并公布Di=C1i+C2i+…+Cni(3) 計算D1+D2+…+Dn，得到總成績。,協(xié)議2（例子）,假設(shè)n=30，學(xué)生P1成績是90，學(xué)生P2成績是30。則相應(yīng)的矩陣可能為：,協(xié)議2的缺點,假設(shè)k個同學(xué)共享信息，可以大概估計出：某兩個學(xué)生Pi和Pj的分?jǐn)?shù)哪個更高。原因：隨機變量Cij為0和Ci之間的隨機數(shù)，因此可以從Cij中得到關(guān)于Ci的統(tǒng)計信息。,協(xié)議3,思想：選取一個數(shù)M，使得Ci

9、j為0和M之間的隨機數(shù)。這樣的好處是：無需擔(dān)心可以從Cij中得到M的任何統(tǒng)計信息。,協(xié)議3,(1) 選取M=101*n，每個學(xué)生Pi產(chǎn)生n-1個1到M之間的隨機數(shù)Cij(i ≠j, 1≤j≤n)，計算Cii，使得Ci=Ci1+Ci2+…+Cin(mod M)，學(xué)生Pi把Cij告訴給學(xué)生Pj。(2) 每個學(xué)生Pi計算并公布Di=C1i+C2i+…+Cni(mod M)。(3) 計算D1+D2+…+Dn (mod M)，得到總

10、成績。,協(xié)議3（例子）,假設(shè)n=30，選取M=101*30=3030。學(xué)生P1成績是90，學(xué)生P2成績是30。相應(yīng)的矩陣可能為：其中矩陣第一行所有值相加等于3120=90(mod 3030)其中矩陣第一行所有值相加等于6090=30(mod 3030),協(xié)議3,分析：協(xié)議3滿足：(1)任何一個學(xué)生都不泄露自己的成績。(2)即使有k個學(xué)生之間相互共享信息，這k個學(xué)生最多也只能知道其余n-k個學(xué)生的平均成績。這

11、是因為：每個學(xué)生Pi從其他學(xué)生那里得到的無非是一些0到M(公開的)之間的隨機數(shù)。,隨機性在協(xié)議3中起的作用,基本思想：把學(xué)生Pi的成績Ci分成n份Ci=Ci1+Ci2+…+Cin（其中n-1個數(shù)都是隨機數(shù)），借助這些隨機數(shù)的“掩護”，Ci中包含的信息才不會被泄露。,3. 驗證一個數(shù)是否為質(zhì)數(shù),,RSA算法,(1)生成兩個大質(zhì)數(shù)p, q………要想保證RSA的安全性，p和q的數(shù)量級應(yīng)為21000。,生成質(zhì)數(shù)的算法,generate

12、Prime(m, n)//生成一個m到n范圍內(nèi)的質(zhì)數(shù)isPrime = false;while(!isPrime)k = rand(m,n);//生成一個m到n范圍內(nèi)的隨機數(shù)isPrime = primilityTesting(k);//驗證n是否為質(zhì)數(shù)return k;如果要生成一個21000數(shù)量級的質(zhì)數(shù)，對primilityTesting算法效率有很高的要求。,“驗證質(zhì)數(shù)”的一個簡單算法,p

13、rimilityTesting(n){for i = 2 to n – 1if (n % i == 0)return false;return true;}算法復(fù)雜度為O(n)，也就是說要驗證一個21000數(shù)量級的數(shù)是否為質(zhì)數(shù)，需要O(21000)的時間。,驗證質(zhì)數(shù)的算法,Miller-Rabin Test是驗證一個數(shù)是否為質(zhì)數(shù)的最常用的方法，也是最著名的隨機算法。我們這里主要介紹該算法的框

14、架結(jié)構(gòu)和整體思想。,Miller-Rabin Test的思想,假定要驗證n是否為質(zhì)數(shù)，該算法驗證n為質(zhì)數(shù)的某個必要條件（存在高效率的算法）。根據(jù)驗證的結(jié)果判斷n是否為質(zhì)數(shù)。這個必要條件就是“費馬小定理”(Fermat’s Little Theorem),費馬小定理,如果一個數(shù)p是質(zhì)數(shù)，那么對于任意的a∈{1,2,…,p-1}, ap-1 = 1 (mod p)。例如，從{1,2,…,p-1}中隨機地選取a=2：7是質(zhì)數(shù)

15、? 2(7-1) = 64 = 1 (mod 7)2(6-1) = 32 = 2 ≠1 (mod 6) ? 6不是質(zhì)數(shù)。,Miller-Rabin Test的思想,如果一個數(shù)p是質(zhì)數(shù)，那么對于任意的a∈{1,2,…,p-1}, ap-1 = 1 (mod p)。例如，從{1,2,…,p-1}中隨機地選取a=2：2(7-1) = 1 (mod 7) ? 7是質(zhì)數(shù)。2(6-1)≠1 (mod 6) ? 6不是質(zhì)數(shù)。,Mi

16、ller-Rabin Test的思想,如果一個數(shù)p是質(zhì)數(shù)，那么對于任意的a∈{1,2,…,p-1}, ap-1 = 1 (mod p)。從{1,2,…,p-1}中隨機地選取a：a(n-1) = 1 (mod n) ? n是質(zhì)數(shù)。(理由不充分)a(n-1)≠1 (mod n) ? n不是質(zhì)數(shù)。(一定成立),Miller-Rabin Test的思想,從{1,2,…,p-1}中隨機地選取a：a(n-1) = 1 (mod

17、n) ? n是質(zhì)數(shù)。(理由不充分)a(n-1)≠1 (mod n) ? n不是質(zhì)數(shù)。(一定成立)如果算法返回“n不是質(zhì)數(shù)”，則n一定不是質(zhì)數(shù)。如果算法返回“n是質(zhì)數(shù)”，則算法有可能“出錯”。事實上，可以證明，“出錯”的概率小于1/2。,Miller-Rabin Test算法,將以下“實驗”重復(fù)進行k次：從{1,2,…,p-1}中隨機地選取a：a(n-1) = 1 (mod n) ? n是質(zhì)數(shù)。(理由不充分)a

18、(n-1)≠1 (mod n) ? n不是質(zhì)數(shù)。(一定成立)(Miller-Rabin Test算法在此基礎(chǔ)上還作了進一步的改進。)如果算法返回“n不是質(zhì)數(shù)”，則n一定不是質(zhì)數(shù)。如果算法返回“n是質(zhì)數(shù)”，則算法有可能“出錯”。事實上，可以證明，“出錯”的概率小于(1/2)k。,隨機算法中一種常用的技巧,在隨機算法的精確度和時間復(fù)雜度之間可以進行交換(trade-off)：代價：算法時間復(fù)雜度以線性的速度上升。收益：算法“失

19、敗”的概率以指數(shù)級的速度下降。,4. 零知識證明（zero-knowledge proof）,,什么是零知識證明？,A向B證明c，證明結(jié)束后B不知道關(guān)于c的任何信息。J.-J. Quisquater et al., "How to Explain Zero-Knowledge Protocols to Your Children," Proc. Advances in Cryptology, pp. 628-63

20、1, 1989.我們舉另外一個例子。,一個直觀的例子,有一個迷宮，A知道這個迷宮從入口s到出口t的n條路徑。假設(shè)A想讓B相信從s到t至少有一條路徑，同時A又不希望向B泄露從s到t的路徑。該采用什么樣的方法？,s,t,,,解決辦法,(1) A選取從s到t的任意一條路徑及路徑上的一個中間點m1。以m1為界，將路徑一分為二：s,…,m1和m1,…,t。A把m1的位置告訴給B。,s,t,,m1,,,解決辦法,(2) B隨機地向A提問：“從s

21、如何到達(dá)m1？”或“從m1如何到達(dá)t？”,s,t,,m1,,,解決辦法,(3) A回答B(yǎng)的問題，B驗證A的答案是否正確。如果正確，則B相信A知道從s到t的路徑。,s,t,,m1,,,分析,從B的角度，假設(shè)A只知道s,…,m1和m1,…,t其中的一條路徑。A能正確回答B(yǎng)的問題的概率為1/2。,s,t,,m1,,,解決辦法&分析,如果把前面的協(xié)議看成一次“隨機實驗”，該實驗失敗的概率為1/2。如果A和B重復(fù)進行該實驗k次，失敗的概

22、率為(1/2)k。當(dāng)k足夠大時， (1/2)k足夠小，k次實驗全部失敗的概率可以忽略不計。,s,t,,m1,,,,,m2,,,,,。。。 。。。,mk,解決辦法&分析,A每次向B提供的信息都是“部分信息”，B不足以從這些部分信息中“拼湊出”從s到t的路徑。,s,t,,m1,,,,,m2,,,,,。。。 。。。,mk,隨機性所起的作用,我們注意到：(2) B隨機地向A提問：“從s如何到達(dá)m1？”或“從m1如何到達(dá)t？”假如

23、A預(yù)先知道B提的問題是：“從s如何到達(dá)m1？”，則A有辦法欺騙B。同樣道理，假如A預(yù)先知道B提的問題是： “從m1如何到達(dá)t？” ，A同樣有辦法欺騙B。,總結(jié),“驗證身份(authentication)”問題,一組用戶A, B, C,…每個用戶都有一個私有信息。假如A想向B表明身份：(1) A向B證明他(她)知道xA。(2) A不希望泄露xA。,數(shù)論基礎(chǔ),為了解決“驗證身份”問題，我們在Zn*上考慮問題:Zn* = {

24、i | 1≤ i ≤n-1, gcd(i, n) = 1}，其中n為兩個不相同質(zhì)數(shù)的乘積。假設(shè)n = 3×7 = 21，Zn* ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}Zn*在乘法操作下，形成一個代數(shù)系統(tǒng)“群(group)”.,游戲時間！,,Zn*中的乘法操作,對任意的a, b∈Zn*，a*b = a*b (mod n)。例如，在Z21*中，2*4 = 8 (

25、mod 21)4*16 = 1 (mod 21)在Zn*中乘法操作是簡單的(regular multiplication & division)。,Zn*中的除法操作,對任意的b∈Zn*，存在唯一的c ∈Zn*，使得b*c = 1 (mod n)我們把c叫做b的倒數(shù)，記為b-1。在Zn*中，已知一個數(shù)b，計算b-1是簡單的(the extended Euclidean algorithm)。,Zn*中的除法操作,對

26、任意的a, b∈Zn*a/b = a*b-1 (mod n)例如，在Z21*中，5/8 = 5*(8-1) = 5*8 = 19 (mod 21)在Zn*中除法操作是簡單的(the extended Euclidean algorithm & regular multiplication and division)。,在Zn*中求平方,對任意的a∈Zn*，a2 = a*a (mod n)例如，在Z21*中，52

27、= 4(mod 21)在Zn*中“求平方”操作是簡單的(regular multiplication & division)。,在Zn*中開平方,對任意的a, b∈Zn*，如果a2 = b (mod n)那么，a叫做b的一個平方根。對于較大的n，在不知道n的質(zhì)因數(shù)分解的情況下，在Zn*中“開方”操作是極其復(fù)雜的。,總結(jié),在Zn*(n為兩個不同質(zhì)數(shù)的乘積)中：,“驗證身份(authentication)”問題,一組用戶A

28、, B, C,…每個用戶都有一個私有信息。假如A想向B表明身份：(1) A向B證明他(她)知道xA。(2) A不希望泄露xA。,“驗證身份(authentication)”問題,選取n為兩個不同大質(zhì)數(shù)p和q的乘積。每個用戶都知道n，但并不知道p或者q。每個用戶i從Zn*中隨機地選取一個數(shù)xi，計算Xi = xi2 (mod n)，并把(i, Xi)公開。,“驗證身份(authentication)”問題,假設(shè)A想向B表明身份

29、，最簡單的辦法：(1) A把xA告訴給B。(2) B驗證xA2 = XA (mod n)是否成立。但這樣做之后，B知道xA，B可以偽裝成A和其他用戶通信。我們需要用到“零知識證明”。,“零知識證明”的思想,A首先生成一個隨機數(shù)y，并計算Y = y2(mod n)。A把關(guān)于xA的信息“拆分”成兩部分，“y”和“y*xA”。(1) 把兩部分信息和在一起，可以得到xA。(2) y對xA起“掩護”作用。,s,t,,Y,,,y

30、,y*xA,類比,解決辦法,(1) A隨機地生成一個數(shù)y∈Zn*，計算Y = y2(mod n)。A把Y告訴給B。,s,t,,Y,,,y,y*xA,解決辦法,(2) B隨機地向A提問：“y等于多少？”或“y*xA等于多少？”,s,t,,Y,,,y,y*xA,解決辦法,(3) A回答B(yǎng)的問題，B驗證A的答案。3.1 問題: “y等于多少?” ? 驗證: y2 = Y (mod n)?3.2 問題: “y*xA等于多少?” ? 驗證

31、: (y*xA)2= Y*XA (mod n)?,s,t,,Y,,,y,y*xA,分析,從B的角度，假設(shè)A只知道“y”或“y*xA” 。A能正確回答B(yǎng)的問題的概率為1/2。,s,t,,,,Y,y,y*xA,解決辦法&分析,如果把前面的協(xié)議看成一次“隨機實驗”，該實驗失敗的概率為1/2。如果A和B重復(fù)進行該實驗k次，失敗的概率為(1/2)k。當(dāng)k足夠大時， (1/2)k足夠小，k次實驗全部失敗的概率可以忽略不計。,s,t,,Y1

32、,,,,,Y2,,,,,。。。 。。。,Yk,解決辦法&分析,A每次向B提供的信息或者是“y”或者是“y*xA”，B不足以從這些隨機信息中得到關(guān)于xA的任何信息。,s,t,,Y1,,,,,Y2,,,,,。。。 。。。,Yk,隨機性所起的作用,我們注意到：(2) B隨機地向A提問：“y等于多少？”或“y*xA等于多少？”假如A預(yù)先知道B提的問題是： “y等于多少？” ，則A有辦法欺騙B。同樣道理，假如A預(yù)先知道B提的問

33、題是： “y*xA等于多少？” ，A同樣有辦法欺騙B。,5. 隨機性方法在數(shù)據(jù)通信中的應(yīng)用,,問題,已知：A和B各有一個文本文件，并且A和B之間通過一條可靠（但昂貴）的通訊線路連接。目標(biāo)：A和B需要比較他們的文本文件是否相同。要求：在A與B之間通訊的數(shù)據(jù)量盡量少。方法：？,問題,,This is my document …,This is my document …,1001011101 …,1001011101 …,A,B

34、,,,,,,?,問題,已知：A和B各有一個二進制序列（二進制數(shù)），并且A和B之間通過一條可靠（但昂貴）的通訊線路連接。目標(biāo)：A和B需要比較他們的二進制序列（二進制數(shù)）是否相同。要求：在A與B之間通訊的數(shù)據(jù)量盡量少。方法：？,方法1,(確定性的方法)A和B事先約定好，A只向B傳輸二進制序列的某些位（比如，奇數(shù)位）。B接收到A傳來的數(shù)據(jù)后，依序跟自己序列的相應(yīng)位（奇數(shù)位）位比較。,方法1的缺點,有時候，方法1能檢測出A與

35、B數(shù)據(jù)的不一致。,有時候，方法1不能檢測出A與B數(shù)據(jù)的不一致。,A: 1011010,B: 1011110,A: 1011010,A: 1111010,,,,,方法1的缺點,條件：假設(shè)A與B的二進制序列長度為n，選取傳輸位的方法為確定性的方法且傳輸位的總位數(shù)小于n。結(jié)論：則總存在某些情況，使得A與B之間數(shù)據(jù)的不一致性永遠(yuǎn)無法得到檢測（檢測出數(shù)據(jù)不一致性的概率為0）。,方法2,(隨機性的方法)A隨機地向B傳輸二進制序列的某些位。

36、B接收到A傳來的數(shù)據(jù)后，依序跟自己序列的對應(yīng)位比較。,方法2的缺點,對于A傳送的每一個比特位，都需要附加相應(yīng)的信息，來表示該比特位對應(yīng)A數(shù)據(jù)的哪一位。該方法能成功地檢測A與B數(shù)據(jù)不一致的概率較低。假設(shè)只傳輸100個比特位，成功驗證兩個長度為100000的比特序列是否一致的概率小于0.1%。,方法2的缺點,假設(shè)A與B的二進制序列長度為n，且其中只有一個比特位不一致。如果A隨機地向B傳送k比特的數(shù)據(jù)，則用方法2能成功地檢測出這

37、種不一致性的概率為： / = k/n 。,方法3,思想：采用傳輸數(shù)據(jù)指紋（fingerprint）的方法。A向B傳送A數(shù)據(jù)的指紋，B核對該指紋是否與自己數(shù)據(jù)的指紋一致。一個數(shù)據(jù)的數(shù)據(jù)指紋中包含原數(shù)據(jù)的特征信息。,,我們前面已經(jīng)提到了，A和B的數(shù)據(jù)都可以看成是二進制序列（二進制數(shù)）。最簡單的生成數(shù)據(jù)指紋的方法：對于一個二進制數(shù)n，其指紋為“n (mod p)”其中p為一個質(zhì)數(shù)。,數(shù)據(jù)指紋的例子,為了直觀

38、起見，我們用十進制數(shù)來解釋數(shù)據(jù)指紋，二進制數(shù)的指紋類似。假設(shè)，n = 8928，選取p = 23：8929 (mod 23) = 4意味著8929在“mod 23”操作下的數(shù)據(jù)指紋為4。,方法2.9999,假定A和B的數(shù)據(jù)分別為xA和xB（位數(shù)為n）A隨機選取一個質(zhì)數(shù)p（位數(shù)最多為m），A向B發(fā)送xA (mod p)。B接收到指紋后，核對xA (mod p) = xB (mod p)是否成立。,方法3,假定A和B的數(shù)據(jù)分別

39、為xA和xB（位數(shù)為n）A隨機選取一個質(zhì)數(shù)p（位數(shù)最多為m），A向B發(fā)送xA (mod p)和p。B接收到指紋后，核對xA (mod p) = xB (mod p)是否成立。,方法3 --- 例子,,,A:8928,mod 23,4,B:8928,mod 23,4,(4, 23),,,,,,,=?,,,,,A: 8928,mod 23,4,B:8944,mod 23,20,(4, 23),,,,,,,=?,,,,,方法3 ---

40、例子,,如果B的數(shù)據(jù)為8928+23*k, 用方法3都會“出錯”。下面我們來分析一下方法3出錯的概率。,A:8928,mod 23,4,B:8951,mod 23,4,(4, 23),,,,,,,=?,,,,,方法3 --- 分析,為了區(qū)分xA和xB (xA≠xB) ，我們隨機地選取一個質(zhì)數(shù)p，進行“mod p”操作：如果p | |xA-xB|， 則xA ≠ xB (mod p)。即：p能將xA和xB區(qū)分開來。如果p | |x

41、A-xB|， 則xA = xB (mod p)。即：p不能將xA和xB區(qū)分開來。,,方法3 --- 分析,Fact #1: 小于等于n的數(shù)中大約有n / ln(n)個質(zhì)數(shù)。Fact #2: 如果x ≤ 2n，則x最多有n個不同的質(zhì)因數(shù)。P[failure]= (|xA-xB|的質(zhì)因數(shù)的個數(shù)) / (1到2m之間的質(zhì)數(shù)的個數(shù))< n / (2m / ln(2m))例如，n=100000，m=32：P[fail

42、ure] ≈ 10-3假設(shè)只傳輸64個比特位，成功驗證兩個長度為100000的比特序列是否一致的概率大概是99.9%。我們還可以通過“重復(fù)進行隨機試驗”的方法提高成功的概率。,6. 隨機性方法在圖論中的應(yīng)用,,圖,定義圖G = (V, E)，其中V為頂點的集合，E為邊的集合。例如，,,,,,,,,,,,,,,,連通圖,在圖G = (V, E)中，p1, p2, …, pn叫做從v到v’的路徑，當(dāng)且僅當(dāng)p1=v, pn=v’，(p

43、i, pi+1) ∈E（1 ≤ i ≤ n-1）。圖G = (V, E)被稱為是連通圖，當(dāng)且僅當(dāng)對任意的v, v’∈V，都存在從v到v’的路徑。,連通度,已知一個連通圖G = (V, E)，如果至少需要從G中去掉c條邊才能使G變?yōu)榉沁B通圖，則c稱為G的連通度(connectivity)。,研究連通度的意義,假設(shè)我們用圖來表示一個局域網(wǎng)：頂點表示局域網(wǎng)中的計算機，邊表示計算機之間的物理連接。則，連通度在一定程度上表示該局域網(wǎng)的可靠程度

44、。假設(shè)我們用圖來表示一個交通網(wǎng)絡(luò)：頂點表示城市，邊表示城市之間的公路。則，連通度在一定程度上表示該交通網(wǎng)絡(luò)的抗阻塞能力。,計算連通度的算法,計算圖連通度的確定性算法是基于網(wǎng)絡(luò)流(network flow)的方法。該算法復(fù)雜，而且效率低。目前，計算圖連通度常用算法是一種隨機算法。和確定性的算法相比，該方法不僅簡單，而且效率較高。,計算連通度的隨機性算法,connectivity(G)//G=(V, E)while(|V|≠2

45、)choose an edge (x, y) at random in G;//在G中隨機選擇一條邊(x, y)contract (x, y);//聚合邊(x, y)return |E|;,分析,給定一個圖G = (V, E)，重復(fù)執(zhí)行connectivity(G) kn2次之后，算法“出錯”的概率小于(1/e)k (其中n為圖G的頂點數(shù)，e為自然對數(shù)的底)。Nick Harvey: “The Bes