강의실/정보영재

문제)


임의의 단순 무향 그래프 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 신고    

    잘 보고 가네요