강의실/정보영재

문제)


임의의 단순 무향 그래프 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를 제외한 모든 경우에 한붓그리기가 가능한 것을 확인 할수가 있습니다.


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









이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
4 0
  • Deborah 2017.12.01 12:09 신고    

    저도 한참을 봐야 알겠네요. 상세한 정답 설명 잘 봤네요

  • 버블프라이스 2017.12.02 05:02 신고    

    저는 한참을 봐도 쉽지가 않은것 같습니다 ';ㅅ;
    정보올림피아드 대회에 출전하시는 학생분들이 이 자료를 보시고 참고를 하시면 아주 좋을것 같습니다.

  • 핑구야 날자 2017.12.02 06:58 신고    

    문제 풀이를 보내 보니 옛날 생각이 나네요 잘 보고 갑니다

  • 청결원 2017.12.03 07:03 신고    

    잘 보고 가네요