臺灣博碩士論文加值系統

Erdős–Rényi隨機圖G(n,p)是有n個點、且任兩點之間獨立地以機率p連結的圖， Bron–Kerbosch演算法在Ο(3^(|V|∕3) )= Ο(〖1.4422〗^(|V|) )時間內找到任何無向圖G=(V,E)的所有最大獨立集合。我們的實驗顯示隨著p增加，G(n,p)的最大獨立集合個數之期望值會先陡增再緩降，而Bron–Kerbosch演算法列舉G(n,p)的所有最大獨立集合所費時間之期望值則先陡增、再陡降、最後緩增。

The Erdős–Rényi random graph G(n,p) is an n-vertex graph which includes each of the (n¦2) edges with probability p independently of all other edges. The Bron–Kerbosch algorithm finds all maximal independent sets of any undirected graph G=(V,E) in Ο(3^(|V|∕3) )= Ο(〖1.4422〗^(|V|) ) time. Our experiments show that as p increases, the expected number of maximal independent sets of G(n,p) increases sharply and then decreases slowly. Furthermore, as p increases, the expected running time of the Bron–Kerbosch algorithm on G(n,p) increases sharply, decreases sharply and then increases slowly.

摘要 i
ABSTRACT ii
誌 謝 iii
Contents iv
1. Introduction 1
2. Experimental Results 5
3. Conclusions 17
References 18

[1]. Bron, Coen; Kerbosch, Joep (1973), “Algorithm 457: finding all cliques of an undirected graph”, Communications of the ACM, Volume 16, Issue 9. Pages 575–577.
[2]. Anil, Maheshwari; Michiel, Smid (2017), “Introduction to Theory of Computation”, Carleton University.
[3]. Douglas B. West (2000), “Introduction to Graph Theory”, 2nd, Pearson.
[4]. Réka Albert; Albert-László Barabási (2002), “Statistical mechanics of complex networks”, Springer.