정보올림피아드 지역대회 2017년 중등부 12번 문제 풀이

문제)

임의의 단순 무향 그래프 G=(V,E)의 라인 그래프(line graph) L(G)=(V’,E’) 는 아래와 같이 정의된다. V’=E 이며, E’={(e,e’)|e와 e’는 G에서 공통된 인접 정점을 갖는다 아래 그림은 어떤 다섯 개의 그래프 G1,G2,G3,G4,G5의 라인그래프를 나타낸 것이다. 이 중에서 원래 그래프가 한붓그리기가 불가능한 것은 무엇일까?

정답) G2

풀이)

라인 그래프는 연결되어 있는 선을 정점으로 하는 그래프 입니다.

참고 : https://ko.wikipedia.org/wiki/%EC%84%A0_%EA%B7%B8%EB%9E%98%ED%94%84

예를 들면 다음과 같습니다.

이러한 그래프를 라인 그래프로 변경해 보면 

위와 같이 표현 할 수 있습니다.

각각의 라인을 정점으로 표현 하는 것입니다.

원래 그래프에서 Edge 는 (1,2) (1,3) (1,4) (4,3) (4,5) (2,5) 가 있고 이들 Edge 가 만나는 구성을 표현 한것이 아래 그림인것입니다.

따라서 보기에 주어진 각각의 라인그래프를 원래의 그래프로 변환 하여 보면 다음과 같습니다.

G1

G2

G3

G4

G5

위와 같이 원 그래프로 표현해 볼수가 있는데요...

한붓그리기가 안되는 것은 G2 가 안되는 것을 확인 할수가 있습니다.

한붓그리기가 가능한 경우는 한 정점에 연결되어 있는 모서리(Edge) 갯수가 모두 짝수개 이거나 또는 홀수개는 2개만 존재할때 입니다.

또한 한붓그리기에서 자기자신에서 출발해서 자기자신으로 돌아오는 경우는 모서리 갯수가 모두 짝수 인경우만 가능합니다.

이 문제에서는 자기자신으로 돌아오는 문제가 아니기 때문에..

원그래프를 만든 후에 모서리 갯수가 짝수개 또는 홀수개가 2개인 경우는 가능하므로 G2를 제외한 모든 경우에 한붓그리기가 가능한 것을 확인 할수가 있습니다.

정보올림피아드 문제 풀이 리스트 정리