| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1999년 12월 22일 수요일 오후 10시 59분 44초 제 목(Title): Re: 그래프 + 확률 문제 이 문제는 상당히 유명한 문제입니다. (Random graph theory의 가장 기초 문제 중의 하나..) 정확한 값을 구하는 식은 엄청 지저분할테고 보통 적당한 bound에서 끝냅니다. 게다가 n이 무한대로 갈 때의 연결 확률을 구하는게 이 동네의 문제라서... 연결 확률이 (ln n)/n 보다 큰 경우엔 n 값이 커질 경우에 연결될 확률이 1이 되며 작은 경우엔 n 값이 커질 경우에 연결될 확률이 0이 됩니다. 증명 아이디어는 전체를 S와 ~S의 두 집합으로 나눌 때에 이 사이에 edge가 없을 확률을 구하고 이걸 모든 가능한 subset S에 대해서 반복하면 됩니다. (그럼 원 확률보다 큰 bound를 얻겠죠?) 이렇게 만든 그래프가 planar냐, hamiltonian path를 가지고 있냐 등등의 문제도 있습니다. -- 박.. |