2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/정보영재

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

원당컴퓨터학원 2017. 12. 1. 09:51

문제)


임의의 단순 무향 그래프 G=(V,E)의 라인 그래프(line graph) L(G)=(V,E)는 아래와 같이 정의된다. V=E 이며, E={(e,e)|eeG에서 공통된 인접 정점을 갖는다 아래 그림은 어떤 다섯 개의 그래프 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를 제외한 모든 경우에 한붓그리기가 가능한 것을 확인 할수가 있습니다.


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









사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기