라도 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''라도 그래프'''({{llang|en|Rado graph}})는 사실상 유일한 [[가산 무한]] 무작위 그래프이다.

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

=== 무작위 그래프 ===
집합 <math>V</math> 위에, 각 <math>\{\{u,v\}\colon u,v\in V,\;u\ne v\}</math>에 변이 존재하는지 여부를 무작위로 결정하자. 각 변은 독립 [[확률 변수]]이며, 각 변이 존재할 확률은 <math>p\in(0,1)</math>라고 하자.

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

=== 이진수를 통한 정의 ===
[[파일:Rado graph.svg|thumb|right|라도 그래프의 이진수를 통한 정의]]
라도 그래프는 [[이진수]]를 사용하여 정의할 수 있다.

'''라도 그래프''' <math>R</math>의 꼭짓점 집합은 [[자연수]]의 집합이다.
:<math>V(R)=\mathbb N=\{0,1,2,\dots\}</math>
두 꼭짓점 <math>m,n\in\mathbb N</math> (<math>m<n</math>) 사이에 변이 존재하는지 여부는 다음과 같다.
* <math>n</math>의 [[이진수]] 표기법에서 <math>m</math>번째 자릿수가 1이라면, <math>(m,n)\in E(R)</math>이다.
여기서 자릿수는 오른쪽부터 세며, 가장 오른쪽의 자릿수를 0번째로 간주한다.

== 성질 ==
라도 그래프의 지름({{llang|en|diameter}})은 2이다. 즉, 임의의 두 꼭짓점 사이에 길이 2 이하의 [[경로 (그래프 이론)|경로]]가 존재한다.

[[그래프]] <math>G</math>가 다음 조건을 만족시키면, '''확대 성질'''({{llang|en|extension property}})을 갖는다고 한다.
* 임의의 두 [[유한 집합]] <math>S,T\subset V(G)</math>에 대하여, 만약 <math>S\cap T=\varnothing</math>이라면, 모든 <math>s\in S</math>에 대하여 <math>sx\in E(V)</math>이며 모든 <math>t\in T</math>에 대하여 <math>tx\not\in E(V)</math>인 <math>x\in V(G)\setminus(S\cup T)</math>가 존재한다.
라도 그래프는 확대 성질을 갖는 유일한 [[가산 집합|가산]] 그래프이다.

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

라도 그래프에서 유한 개의 꼭짓점 <math>S\subset V(R)</math>을 삭제하여도 라도 그래프와 동형이다.
:<math>R\cong R\setminus S</math>
마찬가지로, 유한 개의 변 <math>T\subset E(R)</math>을 삭제하여도 라도 그래프와 동형이다.
:<math>R\cong R\setminus T</math>

== 역사 ==
[[빌헬름 아커만]]({{llang|de|Wilhelm Ackermann}})이 1937년에 정의하였다.<ref>{{저널 인용|journal=Mathematische Annalen
|날짜=1937|volume= 114|issue =1|pages= 305-315
|title=Die Widerspruchsfreiheit der allgemeinen Mengenlehre
|first=Wilhelm |last=Ackermann|doi=10.1007/BF01594179|zbl=0016.19501|jfm=63.0828.04|언어=de}}</ref> [[에르되시 팔]]과 [[레니 얼프레드]]({{llang|hu|Rényi Alfréd}})가 이 그래프가 유일한 무작위 그래프라는 것을 보였다.<ref>{{인용
 | last = Erdős | first = P. | authorlink = 에르되시 팔
 | 공저자 = A. Rényi
 | doi = 10.1007/BF01895716
 | mr = 0156334
 | journal = Acta Mathematica Academiae Scientiarum Hungaricae
 | pages = 295–315
 | title = Asymmetric graphs
 | volume = 14
 | 날짜 = 1963 | issn= 0001-5954 | zbl = 0118.18901 | 언어=en}}</ref>
[[리하르트 라도]]가 1964년에 재발견하였으며, 모든 가산 그래프를 유도 부분 그래프로 포함한다는 것을 보였다.<ref>{{저널 인용|first=Richard|last=Rado|저자링크=리하르트 라도|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa9/aa9133.pdf|title=Universal graphs and universal functions|journal=Acta Arithmetica|날짜=1964|volume=9|pages=331–340|issn=0065-1036|zbl=0139.17303|언어=en}}</ref>

== 각주 ==
{{각주}}
* {{서적 인용|제목=Graph theory|총서=Graduate Texts in Mathematics|권=173|성=Diestel|이름=Reinhard|판=4판|날짜=2010|isbn= 978-3-642-14278-9|url=http://diestel-graph-theory.com/|zbl=1204.05001|언어=en}}
* {{서적 인용 | last=Marker | first=David | title=Model theory: an introduction | publisher=Springer | 날짜=2002 | doi = 10.1007/b98860 | isbn = 978-0-387-98760-6 |총서=Graduate Texts in Mathematics|권=217|issn=0072-5285|zbl=1003.03034|언어=en}}

[[분류:그래프]]