| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1999년 12월 23일 목요일 오후 12시 44분 49초 제 목(Title): Re: 그래프 + 확률 문제 연결 확률 p 가 n에 관한 함수 p(n) = (ln n)/n + c/n 라고 할 때(c는 상수) lim{n->inf} Pr[G(n,p) is connected] = exp{-exp(-c)} 라는 결과가 있습니다. 이 증명의 main idea는 그래프가 disconnect되었다고 할 경우, 대부분이 하나의 node만 떨어져나간다는 관찰(하나의 node가 떨어지려면 n-1개의 edge만 지우면 되지만.. k개짜리 덩어리가 떨어져 있으려면 대락 n^k 개의 edge가 없어야 하므로 거의 무시해도...) * G(n,p)는 n개의 노드가 각 노드쌍 사이에 p의 확률로 edge를 연결해 만든 random graph. Erdos와 Renyi가 1960년에 낸 결과입니다. "Magyar Tud. Akad. Mat. Kut. Int. Kozl."이란 Journal이나 Conference, Workshop이 있나요? 여기 나와있다고... 혹시 이런 문제(굶어죽기 전에 하면 재미있을.. --;)에 관심있는 분을 위해서 책을 소개하자면 (제가 아는게 아니라 제가 보는 책에 나와있는 ref..) B. Bollobas, Random Graphs, Academic Press, 1985 E. Palmer, Graphical Evolution, John Wiley, 1985 Joen Spencer, Ten Lectures on the Probabilistic Method, 2nd ed., SIAM, 1994 입니다. (제가 가지고 있는 건 3번째 책입니다. random graph를 연구하는 데는 도움이 안 되고 대충 맛보기 정도로 쓸만한 책인듯...) -- 박.. |