5
이 문제는 그래프 이론에 답이 있어야하는 것처럼 느껴지지만, 내가 아는 그래프 이론 문제와 정확히 일치하지는 않습니다. (참고 : 실제로는 현실 세계의 문제이며 쉽게 읽을 수 있도록 허구 화 된 것입니다.)그래프에서 "페어링"을 만드시겠습니까?
내 집에서 체스 플레이어가 짝수 그룹이라고 상상해보십시오. 나는 테이블과 체스 세트를 모두 가지고 놀 수 있지만, "Pairing"(그래프 이론 용어가 있는지 확실하지 않음)이나 모든 사람들이 누군가를 연기 할 수있는 matchups 목록을 만들어야합니다. 체스 선수들은 이전에 한번도 해본 적이없는 사람과 놀고 싶어합니다.
각 플레이어의 선수 명단을 가지고 있다면 이전 매치업을 보여주는 그래프를 쉽게 만들 수 있습니다. 예를 들어, A가 B와 C를 연주 한 말을, C는 D을했다 :
A----B
|
|
C----D
내가 B를 일치 수 있다는 사실을 알고는/C 및 A/D가 페어링을 만들 수 있습니다.
그러나 이전 매치업의 그래프는 다음과 같습니다 경우 :A----B
\ |
\ |
C D
은 그 때 나는 페어링을 만들 수 없습니다. B는 C 만 재생할 수 있습니다. 그러면 A와 D (이미 연주 한 사람)가 서로 연주하게됩니다.
그래서 (페니스 이외의 다른 방법을 통해) 페어링을 만들 수 있는지 여부를 어떻게 알 수 있습니까? 내가 찾고있는 트리 나 사이클은 아니지만 테스트 할 수있는 다른 그래프 속성이 있습니까?