랜덤 그래프, 연결 그래프, 폴 에어디쉬

랜덤 그래프¶

랜덤 그래프는 문자 그대로의 뜻을 가지고 있다. 무작위로 생성된 연결선들이 있는 그래프인 것이다. 그래프를 생성할 수 있는 무작위 프로세스는 당연히 여러 가지 종류가 있으며, 그래서 랜덤 그래프의 종류도 여러 가지다. 그 중에서 흥미로운 것이 G(n,p)로 나타내는 에어디쉬-레니 모델이다. 해석하자면 두 개의 노드 사이에서 연결선이 존재할 확률이 p일 때, n개의 노드로 된 그래프를 생성하는 모델이다.
참고 : http://en.wikipedia.org/wiki/Erdos-Renyi_model

연결 그래프¶

모든 노드에서 다른 모든 노드로 경로가 존재할 때 그 그래프는 연결되었다고 말한다.
참고 : http://en.wikipedia.org/wiki/Connectivity_(graph_theory)

그래프가 연결되었는지를 확인하는 간단한 알고리즘이 있다. 아무 노드에서나 탐색을 시작해서 닿을 수 있는 모든 노드를 표시하는 것이다. 그리고 나서 모든 노드에 표시가 되었나를 확인해 보면 된다.
참고 : http://en.wikipedia.org/wiki/Breadth-first_search

일반적으로 노드를 처리할 때, 그 노드를 '방문(visit)'한다고 말한다.

탐색에서는 노드를 표시함으로써 그 노드를 방문하고(나중에 그 노드에 방문했었는지를 알 수 있도록), 그 다음에 연결된 노드 중에서 표시가 되어있지 않은 노드들을 방문한다.

너비 우선 탐색에서는 노드가 발견되는 순서대로 노드들을 방문하게 된다. 큐 또는 '작업 목록'을 사용해서 순서를 정리해 둘 수 있다. 어떻게 동작하는지 한 번 보자.

1. 아무 노드에서나 시작해서 그것을 큐에 추가한다.

2. 큐에서 노드를 하나 꺼내서 표시한다. 만약 그 노드가 표시되지 않은 노드에 하나라도 연결되어 있다면, 그것들을 큐에 추가한다.

3. 큐가 비어있지 않다면 2단계로 돌아간다.

폴 에어디쉬: 이동해 다니는 수학자, 스피드광¶

폴 에어디쉬는 헝가리 수학자로 경력 대부분을 떠돌아 다니며 전세계 대학들의 동료를 방문하고 500명이 넘는 연구자들과 공동으로 논문을 썼다.

그는 악명 높은 카페인 중독자로 알려져 있는데, 죽기 직전 20년 동안은 암페타민의 열혈 사용자였다고도 한다. 그는 자신의 생산성을 이러한 약물들의 결과라고 보았다. 내기에서 이기기 위해 한 달 동안 약을 끊은 다음에 그가 말하기를 내기의 유일한 결과는 수학이 한 달 퇴보한 것이라고 할 정도였다.

1960년대에 그와 알프레드 레니는 에어디쉬-레니 랜덤 그래프 모델을 소개하고 속성에 대해 연구한 일련의 논문을 썼다. 그 중 두 번째 논문은 http://www.renyi.hu/~p_erdos/1960-10.pdf 에서 받을 수 있다.

그들이 발견한 가장 놀라운 결과는, 랜덤 그래프에 무작위 연결선들이 추가될 때 나타나는 갑작스러운 특성 변화였다. 그들은 여러 가지 그래프 속성들에서, 어떤 값 이하에서는 해당 속성이 희귀하지만 그 값 이상에서는 거의 확정적이게 만드는 확률 p의 문턱값이 있다는 사실을 보여주었다. 이러한 전환은 때로는 '상변화'라고도 하는데 어떤 임계 온도를 기준으로 상태가 변화하는 물리계에 비유한 것이다.
http://en.wikipedia.org/wiki/Phase_transition 를 참고하자.

출처: 복잡계와 데이터 과학