라도 그래프

그래프 이론에서 라도 그래프(영어: Rado graph)는 사실상 유일한 가산 무한 무작위 그래프이다.

정의

라도 그래프는 여러 방법으로 정의할 수 있다.

무작위 그래프

집합 $V$ 위에, 각 $\{\{u,v\}\colon u,v\in V,\;u\neq v\}$에 변이 존재하는지 여부를 무작위로 결정하자. 각 변은 독립 확률 변수이며, 각 변이 존재할 확률은 $p\in (0,1)$라고 하자.

만약 $V$가 가산 무한 집합이라면, 이렇게 하여 얻는 그래프는 $p$의 값에 관계 없이, 거의 확실하게 하나의 그래프와 동형이다. 이 그래프를 라도 그래프 $R$라고 한다.

이진수를 통한 정의

라도 그래프의 이진수를 통한 정의

라도 그래프는 이진수를 사용하여 정의할 수 있다.

라도 그래프 $R$의 꼭짓점 집합은 자연수의 집합이다.

$V(R)=\mathbb {N} =\{0,1,2,\dots \}$

두 꼭짓점 $m,n\in \mathbb {N}$ ($m<n$) 사이에 변이 존재하는지 여부는 다음과 같다.

• $n$의 이진수 표기법에서 $m$번째 자릿수가 1이라면, $(m,n)\in E(R)$이다.

여기서 자릿수는 오른쪽부터 세며, 가장 오른쪽의 자릿수를 0번째로 간주한다.

성질

라도 그래프의 지름(영어: diameter)은 2이다. 즉, 임의의 두 꼭짓점 사이에 길이 2 이하의 경로가 존재한다.

그래프 $G$가 다음 조건을 만족시키면, 확대 성질(영어: extension property)을 갖는다고 한다.

• 임의의 두 유한 집합 $S,T\subset V(G)$에 대하여, 만약 $S\cap T=\varnothing$이라면, 모든 $s\in S$에 대하여 $sx\in E(V)$이며 모든 $t\in T$에 대하여 $tx\not \in E(V)$인 $x\in V(G)\setminus (S\cup T)$가 존재한다.

라도 그래프는 확대 성질을 갖는 유일한 가산 그래프이다.

확대 성질을 갖는 그래프는 임의의 가산 그래프를 유도 부분 그래프로 포함한다. 이는 수학적 귀납법으로 쉽게 보일 수 있다.

라도 그래프에서 유한 개의 꼭짓점 $S\subset V(R)$을 삭제하여도 라도 그래프와 동형이다.

$R\cong R\setminus S$

마찬가지로, 유한 개의 변 $T\subset E(R)$을 삭제하여도 라도 그래프와 동형이다.

$R\cong R\setminus T$

역사

빌헬름 아커만(독일어: Wilhelm Ackermann)이 1937년에 정의하였다. 에르되시 팔과 레니 얼프레드(헝가리어: Rényi Alfréd)가 이 그래프가 유일한 무작위 그래프라는 것을 보였다. 리하르트 라도가 1964년에 재발견하였으며, 모든 가산 그래프를 유도 부분 그래프로 포함한다는 것을 보였다.

참고 문헌

• Diestel, Reinhard (2010). 《Graph theory》. Graduate Texts in Mathematics (영어) 173 4판. ISBN 978-3-642-14278-9. Zbl 1204.05001.  CS1 관리 - 추가 문구 (링크)
• Marker, David (2002). 《Model theory: an introduction》. Graduate Texts in Mathematics (영어) 217. Springer. doi:10.1007/b98860. ISBN 978-0-387-98760-6. ISSN 0072-5285. Zbl 1003.03034.