본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대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.10 2020.02.03

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

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

      멘토의 검토 결과  [문제1] 답은 맞지만 설명을 좀 더 보완해주면 좋겠다고 합니다. “마찬가지” 부분이요.

      좋아요0
  •  
    아인수타인 Lv.11 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      최기자 Lv.4 2020.03.05

      답변 늦어서 미안해요~.김다인 멘토가 아래와 같은 코멘트를 줬어요.

       

      닫힌 그래프 = 회로 인가요? 그리고 닫힌 그래프를 포함하지 않더라도 가능한 그래프는 많아요! 8비트 컴퓨터 친구가 제시한 답안을 참고해주세요~

      좋아요0
  •  
    아인수타인 Lv.11 2020.02.03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      최기자 Lv.4 2020.03.05

      김다인 멘토가 "문제1과 비슷한 맥락으로 다시 생각해보세요!"라는 코멘트를 줬습니다.^^

      좋아요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 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      8비트 컴퓨터 Lv.5 2020.02.03 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      최기자 Lv.4 2020.03.05

      멘토의 검토 결과  문제1과 비슷한 맥락으로 설명이 부족합니다. 왜 이런 그래프만 가능한지 설명해주세요!

      좋아요0
  •  
    code Lv.4 2020.02.04
    확인요청중

    댓글 작성하기 좋아요0 댓글수10
    •  
      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
    •  
      최기자 Lv.4 2020.03.05

      검토가 늦어서 미안합니다~!

       

      [문제3] 원을 그리는 방법을 좀 더 명확하게 설명해주세요.

       

      [문제1] Lemma 1이 왜 P_4를 포함하지 않는 그래프가 4개라고 설명해주나요? 그리고 Lemma1에서 ‘한붓그리기’가 통상 생각하는 ‘한붓그리기’의 정의와 일치하지 않는 것 같아요!

       

      [문제2] n개의 점으로 이루어진 그래프로부터 n+1개의 점을 가지는 그래프를 만들어내려고 하고 있어요. 하지만 이 논리를 쓰려면 n+1개의 점을 가지는 그래프는 항상 n개의 점으로 이루어진 문제의 조건을 만족하는 그래프를 가지고 있다는 것을 증명해야합니다. 원래의 그래프가 P_k를 포함하지 않았다면 점을 하나 제거해도 P_k를 포함하지 않는다는 점이 당연하게 받아들여졌을 거에요. 하지만 ‘연결성’도 마찬가지일까요? 즉, 점을 하나 제거해도 원래 그래프가 연결그래프이도록 할 수 있나요? [문제4] “무한개의 점”을 가지는 그래프는 생각할 수 없어요.
       

      좋아요0
    •  
      code Lv.4 2020.03.05

      문제1. lemma1을 빼고 그냥 이렇게 해도 되나요?

                'P4를 포함하지 않는 점 4개의 연결 그래프를 찾으면...'

      문제2. 코멘트가 이해가 안가요.... 진짜 열심히 봤는데 무엇이 엄밀하지 못한지를 모르겠습니다.

      문제3. 기준 점이나 사이클은 어디를 잡아도 상관없습니다. 그 기준에 대해서 최소 n개의 간선으로 연결되는 각각의 모든 점에대해 n에 대한 같은 홀짝성을 가지면 같은색으로 칠하고 다르면 다른색으로 칠한다는 것을 원으로 표현한것입니다. n=0일때의 사이클을 제외하고요.

      문제4. 음.. 그렇다면 이 문제는 생각보다 어렵겠네요.... 좀 더 생각해봐야겠습니다.

      검토해주셔서 감사합니다.

      좋아요0
  •  
    code Lv.4 2020.02.04 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      최기자 Lv.4 2020.02.19 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      code Lv.4 2020.02.19 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    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
  •  
    무한대의끝을본남자 Lv.6 2020.03.19

    c언어에서 그래프에대하여 배웠었는데 재밌는문제지만 최신문제에 집중하고 이것은 나중에 풀겠습니다

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