조합[램지의 정리] 2-3

램지의 정리를 처음 보는 분들이라면 고든 램지를 떠올렸을 수도 있을 것 같다. 하지만 이번에 배울 램지의 정리는 고든 램지에 당연히 아무 관련없는 정리이다. 램지의 정리에 대해 설명하기에 앞서, 완전그래프 Kn에 대해 먼저 알고 있어야 한다. Kn은 n개의 점이 존재하고 어떤 2개의 점을 잡아도 점과 점이 연결되어 있는 상태를 말한다. 위에 보이는 사진이 바로 K4 완전그래프이다. 4개의 점이 존재하고 어떤 2개의 점을 잡아도 직접적으로 이어져 있는 것이 확인된다. R(a,b)=n이라면 Kn의 각 선분을 2가지 색으로 임의로 색칠시 항상 Ka나 Kb가 존재하게 된다는 뜻이다. 백문이불여일견이라고 아래의 예시로 이해를 도와보겠다. ※주의사항:램지이론은 완전그래프에서만 사용할 수 있다. #1.9명의 사람 가..

2021.11.07