본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 대38. 특수한 구조를 갖는 그래프 색칠하기
수학동아 2020.02.03

이번 대학수학회 문제에서는 특정한 그래프를 부분 그래프로 갖지 않는 그래프의 채색 문제에 대해 다뤄보도록 하자. 먼저 문제에 필요한 그래프의 용어를 정의하자. (그래프의 정의와 기초 용어는 대한수학회 문제 12호를 참고하기 바란다)

 

정의 1] 그래프 G채색은 연결된 두 꼭짓점이 서로 다른 색을 갖도록 꼭짓점을 색칠하는 것을 말하고, 이때 필요한 최소한의 색의 수를 G채색수라 한다. 예를 들어, 길이가 짝수인 순환 그래프(cycle)의 채색수는 2, 길이가 홀수인 순환 그래프의 채색수는 3이다. (순환 그래프는 아래와 같이 생긴 그래프이다.)

 

 

정의 2] 그래프 G H에 대해, G의 변과 꼭짓점을 지워서 H를 만들 수 있으면 H G부분 그래프라 한다. (, 꼭짓점을 지울 때는 그 꼭짓점과 연결된 변도 모두 지운다.) 그리고 H G의 부분 그래프가 아닐 때, ‘G H를 포함하지 않는다’고 한다. 아래 그림에서 H_{1} G에서 빨간색 변을 지우면 얻을 수 있지만, H_{2}G로부터 얻을 수가 없다. 따라서, G H_{1}을 포함하고, H_{2}는 포함하지 않는다.

 

 

정의 3] 자연수 k에 대하여, 그래프 P_{k}는 꼭짓점 집합 V=\left \{ v_{1}, v_{2}, \cdots , v_{k} \right \}와 변의 집합 E(P_{k})=\left \{ v_{1}v_{2}, v_{3}v_{4}, \cdots , v_{k-1}v_{k} \right \}로 구성된 그래프다. 이런 그래프를 경로 그래프라 한다.

 

 

이제 문제를 풀어보도록 하자. P_{1}을 포함하지 않는 그래프는, 꼭짓점이 하나도 없는 그래프이므로 채색수가 0이다. P_{2}를 포함하지 않는 그래프는, 변이 하나도 없는 그래프이므로 채색수가 1이하이다. 그렇다면, P_{3}를 포함하지 않는 그래프의 채색수는 최대 몇일까? 그래프 G P_{3}를 포함하지 않는다면, G의 모든 꼭짓점은 차수가 1이하여야 한다. 그러므로 G의 연결성분은, 아래 그림처럼 하나의 꼭짓점으로 구성돼 있거나, 연결된 두 꼭짓점으로 구성돼 있어야 한다. 따라서,  G의 채색수는 2 이하다. 비슷한 방법으로 P_{4}를 포함하지 않는 그래프, P_{5}를 포함하지 않는 그래프의 채색수의 최댓값을 구할 수 있다.

 

왼쪽 그래프는 P_{3}를 포함하지 않지만, 오른족 2개 그래프는 P_{3}를 포함한다.

 

 

문제 1. 그래프 G P_{4}를 포함하지 않는 그래프다.

1-1. G의 연결성분으로 가능한 그래프를 모두 찾아라.

1-2. G의 채색수의 최댓값은?

 

 

문제 2. 그래프 G P_{5}를 포함하지 않는 그래프다.

2-1. G의 연결성분으로 꼭짓점의 개수가 5개 이상인 그래프를 모두 찾아라.

2-2. G의 채색수의 최댓값은?

 

 

문제 3.이상인 각각의 자연수 k에 대해, P_{k}를 포함하지 않는 그래프의 채색수의 최댓값을 구하여라.

 

위의 문제들로부터, 주어진 경로 그래프를 포함하지 않는 그래프의 채색수는 유한하다는 것을 알 수 있었다. 이 문제를 트리 그래프로 확장해보자. (‘트리 그래프는 회로가 없는 연결 그래프이다.)

 

 

문제 4. 다음 조건을 만족하는 상수 c_{T}가 존재하는 트리 그래프 T를 모두 찾아라. 그리고 이때, 가능한 c_{T}의 최솟값을 구하라.

조건: T를 포함하지 않는 그래프의 채색수는 c_{T} 이하다.

 

  •  
    sicma Lv.9 2020.02.03

    이번 대한수학회문제 그나마 이해되네요.

    댓글 작성하기 좋아요0 댓글수0
  •  
    8비트 컴퓨터 Lv.5 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
  •  
    아인수타인 Lv.11 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    아인수타인 Lv.11 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    아인수타인 Lv.11 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      8비트 컴퓨터 Lv.5 2020.02.03

      헉,,,, 벌써 다 풀었나요

      좋아요0
    •  
      아인수타인 Lv.11 2020.02.04

      1,2,3번은 풀었는데 4번은 모르겠네요...

      좋아요0
    •  
      아인수타인 Lv.11 2020.02.04 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    8비트 컴퓨터 Lv.5 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
  •  
    code Lv.4 2020.02.04
    확인요청중

    댓글 작성하기 좋아요0 댓글수8
    •  
      8비트 컴퓨터 Lv.5 2020.02.04

      아 2-2번 그걸 생각 못했네 ...+ㅡ*

      근데 2-1에서 조건이 점이 5개 이상인 그래프인데 4개짜리도 포함시키신건 아니죠?

      좋아요0
    •  
      code Lv.4 2020.02.04

      4개이하의 노드를 갖는 그래프는 당연히 비포함입니다~

      점 4개의 그래프를 그린것은 접근 과정을 토대로한 명확한 분류를 위해서입니다 ㅎㅎ

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.02.06

      3번 풀이의 2번 경우에서 두 개 이상의 사이클이 변을 공유하고 있는 경우도 고려해줘야 하지 않나요? 또는 어떤 사이클에 원을 그려줄지 정하는 방법이 있어야 할 것 같아요. 

      좋아요0
    •  
      code Lv.4 2020.02.06

      좋은 지적 감사합니다.

      완전한 답변이 될진 모르겠네요.

      사이클이 2개이상 독립적으로 발생한경우) 각각의 사이클은 서로의 채색수에 영향을 주지 못하기에, 각사이클중 최대의 채색수가 최댓값이 됩니다. - > k-1보다 많을일 없음

      그외의 경우) 이것에 대해서는 이미 증명한것으로 생각합니다.

       

      +'독립'의 기준

      서로의 사이클은 두 점이상으로 연결되지 않음. 

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.02.09

      어.. 혹시 그 외의 경우는 어떻게 증명되었는지 간략하게라도 설명해주실 수 있나요? 

      좋아요0
    •  
      code Lv.4 2020.02.09

      두 개 이상의 사이클이 변을 공유한다면, 그것은 하나의 사이클로 볼 수 있습니다.

      명확하게, 제가 사이클의 정의를 정확하게 이해하지 못했을 수도 있고 그래서 그것이 사이클이 아니더라도,

      위에서 말한 '사이클'로 보는데에는, 문제가 없다고 생각합니다.

      따라서 위에 써있는 풀이를 적용할 수 있습니다.

      혹시 잘못된 점이 있다면 말씀해주세요. 

      좋아요0
    •  
      code Lv.4 2020.02.09

      그리고 이 풀이의 핵심은, 최종적으로 사이클을 구성하는 점갯수가 k개를 넘지 못하기 때문에 k-1 채색수를 넘지 못한다는 것입니다.

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.02.12

      이해됐습니다. 친절한 설명 감사합니다!

      좋아요0
  •  
    code Lv.4 2020.02.04 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      최기자 Lv.4 2020.02.19 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      code Lv.4 2020.02.19 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    LCA문제풀어주세요 Lv.10 2020.02.04

    1번에서 P3을 포함하고 있는 G는 점이 항상 3개여야 하나요?

    댓글 작성하기 좋아요0 댓글수3
    •  
      8비트 컴퓨터 Lv.5 2020.02.04

      아뇨 1개여도 되요...

      좋아요0
    •  
      code Lv.4 2020.02.04

      점 3개이상이면 포함 할 수도 있습니다.

      질문에 맞는 대답인지 모르겠네요.

      좋아요0
    •  
      8비트 컴퓨터 Lv.5 2020.02.04

      아 죄송해요 질문을 잘못 보고 이해했습니다

      좋아요0
  •  
    8비트 컴퓨터 Lv.5 2020.02.04

    흠... 이 정도 속도이면 이 문제 일주일 컷 당할 듯...

    댓글 작성하기 좋아요0 댓글수0
  •  
    8비트 컴퓨터 Lv.5 2020.02.04

    code님 4번도 푸셨나요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      code Lv.4 2020.02.04

      음.. 적어놓은 것이 4번이긴한데요.. 확신은 잘 서지 않습니다.

      혹시라도 정답일 수 있으니까 비댓으로 처리한것입니다.

      좋아요0
  •  
    아인수타인 Lv.11 2020.02.05 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    수학꿀잼 Lv.1 2020.02.08

    겨울학교에서 어떤분께서 크로마틱수 강의하셨는데 이번 주제랑 겹칠줄 몰랐네요.

    댓글 작성하기 좋아요0 댓글수0