이번 대학수학회 문제에서는 특정한 그래프를 부분 그래프로 갖지 않는 그래프의 채색 문제에 대해 다뤄보도록 하자. 먼저 문제에 필요한 그래프의 용어를 정의하자. (그래프의 정의와 기초 용어는 대한수학회 문제 12호를 참고하기 바란다)
정의 1] 그래프 
의 ‘채색’은 연결된 두 꼭짓점이 서로 다른 색을 갖도록 꼭짓점을 색칠하는 것을 말하고, 이때 필요한 최소한의 색의 수를 
의 ‘채색수’라 한다. 예를 들어, 길이가 짝수인 순환 그래프(cycle)의 채색수는 2, 길이가 홀수인 순환 그래프의 채색수는 3이다. (순환 그래프는 아래와 같이 생긴 그래프이다.)
정의 2] 그래프 
와 
에 대해, 
의 변과 꼭짓점을 지워서 
를 만들 수 있으면 
를 
의 ‘부분 그래프’라 한다. (단, 꼭짓점을 지울 때는 그 꼭짓점과 연결된 변도 모두 지운다.) 그리고 
가 
의 부분 그래프가 아닐 때, ‘
는 
를 포함하지 않는다’고 한다. 아래 그림에서 
은 
에서 빨간색 변을 지우면 얻을 수 있지만, 
는 로부터 얻을 수가 없다. 따라서, 
는 을 포함하고, 
는 포함하지 않는다.
정의 3] 자연수 
에 대하여, 그래프 
는 꼭짓점 집합 
와 변의 집합 
로 구성된 그래프다. 이런 그래프를 ‘경로 그래프’라 한다.
이제 문제를 풀어보도록 하자. 
을 포함하지 않는 그래프는, 꼭짓점이 하나도 없는 그래프이므로 채색수가 0이다. 
를 포함하지 않는 그래프는, 변이 하나도 없는 그래프이므로 채색수가 1이하이다. 그렇다면, 
를 포함하지 않는 그래프의 채색수는 최대 몇일까? 그래프 가 
를 포함하지 않는다면, 의 모든 꼭짓점은 차수가 
1이하여야 한다. 그러므로 의 연결성분은, 아래 그림처럼 하나의 꼭짓점으로 구성돼 있거나, 연결된 두 꼭짓점으로 구성돼 있어야 한다. 따라서, 의 채색수는 
2 이하다. 비슷한 방법으로 
를 포함하지 않는 그래프, 
를 포함하지 않는 그래프의 채색수의 최댓값을 구할 수 있다.
왼쪽 그래프는 
를 포함하지 않지만, 오른족 2개 그래프는 
를 포함한다.
문제 1. 그래프 는 
를 포함하지 않는 그래프다.
1-1. 의 연결성분으로 가능한 그래프를 모두 찾아라.
1-2. 
의 채색수의 최댓값은?
문제 2. 그래프 
는 
를 포함하지 않는 그래프다.
2-1. 
의 연결성분으로 꼭짓점의 개수가 
5개 이상인 그래프를 모두 찾아라.
2-2. 
의 채색수의 최댓값은?
문제 3. 6 이상인 각각의 자연수 에 대해, 
를 포함하지 않는 그래프의 채색수의 최댓값을 구하여라.
위의 문제들로부터, 주어진 경로 그래프를 포함하지 않는 그래프의 채색수는 유한하다는 것을 알 수 있었다. 이 문제를 트리 그래프로 확장해보자. (‘트리 그래프’는 회로가 없는 연결 그래프이다.)
문제 4. 다음 조건을 만족하는 상수 
가 존재하는 트리 그래프 
를 모두 찾아라. 그리고 이때, 가능한 
의 최솟값을 구하라.
조건: 
를 포함하지 않는 그래프의 채색수는 이하다.
아 2-2번 그걸 생각 못했네 ...+ㅡ*
근데 2-1에서 조건이 점이 5개 이상인 그래프인데 4개짜리도 포함시키신건 아니죠?
4개이하의 노드를 갖는 그래프는 당연히 비포함입니다~
점 4개의 그래프를 그린것은 접근 과정을 토대로한 명확한 분류를 위해서입니다 ㅎㅎ
3번 풀이의 2번 경우에서 두 개 이상의 사이클이 변을 공유하고 있는 경우도 고려해줘야 하지 않나요? 또는 어떤 사이클에 원을 그려줄지 정하는 방법이 있어야 할 것 같아요.
좋은 지적 감사합니다.
완전한 답변이 될진 모르겠네요.
사이클이 2개이상 독립적으로 발생한경우) 각각의 사이클은 서로의 채색수에 영향을 주지 못하기에, 각사이클중 최대의 채색수가 최댓값이 됩니다. - > k-1보다 많을일 없음
그외의 경우) 이것에 대해서는 이미 증명한것으로 생각합니다.
+'독립'의 기준
서로의 사이클은 두 점이상으로 연결되지 않음.
어.. 혹시 그 외의 경우는 어떻게 증명되었는지 간략하게라도 설명해주실 수 있나요?
두 개 이상의 사이클이 변을 공유한다면, 그것은 하나의 사이클로 볼 수 있습니다.
명확하게, 제가 사이클의 정의를 정확하게 이해하지 못했을 수도 있고 그래서 그것이 사이클이 아니더라도,
위에서 말한 '사이클'로 보는데에는, 문제가 없다고 생각합니다.
따라서 위에 써있는 풀이를 적용할 수 있습니다.
혹시 잘못된 점이 있다면 말씀해주세요.
그리고 이 풀이의 핵심은, 최종적으로 사이클을 구성하는 점갯수가 k개를 넘지 못하기 때문에 k-1 채색수를 넘지 못한다는 것입니다.
이해됐습니다. 친절한 설명 감사합니다!
검토가 늦어서 미안합니다~!
[문제3] 원을 그리는 방법을 좀 더 명확하게 설명해주세요.
[문제1] Lemma 1이 왜 P_4를 포함하지 않는 그래프가 4개라고 설명해주나요? 그리고 Lemma1에서 ‘한붓그리기’가 통상 생각하는 ‘한붓그리기’의 정의와 일치하지 않는 것 같아요!
[문제2] n개의 점으로 이루어진 그래프로부터 n+1개의 점을 가지는 그래프를 만들어내려고 하고 있어요. 하지만 이 논리를 쓰려면 n+1개의 점을 가지는 그래프는 항상 n개의 점으로 이루어진 문제의 조건을 만족하는 그래프를 가지고 있다는 것을 증명해야합니다. 원래의 그래프가 P_k를 포함하지 않았다면 점을 하나 제거해도 P_k를 포함하지 않는다는 점이 당연하게 받아들여졌을 거에요. 하지만 ‘연결성’도 마찬가지일까요? 즉, 점을 하나 제거해도 원래 그래프가 연결그래프이도록 할 수 있나요? [문제4] “무한개의 점”을 가지는 그래프는 생각할 수 없어요.
문제1. lemma1을 빼고 그냥 이렇게 해도 되나요?
'P4를 포함하지 않는 점 4개의 연결 그래프를 찾으면...'
문제2. 코멘트가 이해가 안가요.... 진짜 열심히 봤는데 무엇이 엄밀하지 못한지를 모르겠습니다.
문제3. 기준 점이나 사이클은 어디를 잡아도 상관없습니다. 그 기준에 대해서 최소 n개의 간선으로 연결되는 각각의 모든 점에대해 n에 대한 같은 홀짝성을 가지면 같은색으로 칠하고 다르면 다른색으로 칠한다는 것을 원으로 표현한것입니다. n=0일때의 사이클을 제외하고요.
문제4. 음.. 그렇다면 이 문제는 생각보다 어렵겠네요.... 좀 더 생각해봐야겠습니다.
검토해주셔서 감사합니다.
폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.
☎문의 02-6749-3911
정기구독 인증방법 안내
