자연계열 II 6번

(라) 유한개의 꼭지점과 이들 꼭지점을 연결하는 유한개의 변으로 이루어진 도형을 ‘그래프’라 부른다. 예를 들어, 아래의 그림 (a)는 열 개의 꼭지점과 아홉 개의 변으로 이루어진 그래프이다. 그림 (b)와 같이 그래프의 모든 변에 방향을 준 것을 ‘유향(有向)그래프’라 하고, 그림 (c)와 같이 부분적으로 방향을 준 것을 ‘준유향그래프’라고 하자.

[문제 6] 네 개의 축구팀이 모든 상대방과 단 한 번씩 경기를 하는 리그전에서 각각의 무승부 경기마다 두 팀에게 모두 1점씩을 부여하고, 각각의 승부가 나는 경기마다 승자와 패자에게 각각 2점과 0점을 부여하여 매 팀의 승점을 계산한다고 하자. 리그전이 모두 끝난 후에 네 팀이 획득한 승점을 크기순으로 나열하여 $\displaystyle a,b,c,d\ (a\ge b\ge c\ge d)$라 하고 각 팀의 이름을 승점으로 정하기로 하자. 예를 들어, a팀은 승점이 a인 팀이고 b팀은 승점이 b인 팀이다. 이렇게 명명된 네 팀을 아래 그림과 같이 그래프 G의 꼭지점에 배치하자. 무승부경기에 해당하는 G의 변에는 방향을 부여하지 않고 승부가 난 경기에 해당하는 G의 변에는 패자에서 승자 쪽으로 방향을 부여하면, G는 제시문 (라)에서 설명한 유향그래프 또는 준유향그래프가 된다. 어떤 팀이 승점 5점을 획득하였고 승점이 같은 팀이 없다고 가정하였을 때, 가능한 유향그래프 또는 준유향그래프 G를 승점 $\displaystyle a,b,c,d$와 함께 모두 제시하시오. [15점]