이번 대학수학회 문제에서는 특정한 그래프를 부분 그래프로 갖지 않는 그래프의 채색 문제에 대해 다뤄보도록 하자. 먼저 문제에 필요한 그래프의 용어를 정의하자. (그래프의 정의와 기초 용어는 대한수학회 문제 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. 음.. 그렇다면 이 문제는 생각보다 어렵겠네요.... 좀 더 생각해봐야겠습니다.
검토해주셔서 감사합니다.
c언어에서 그래프에대하여 배웠었는데 재밌는문제지만 최신문제에 집중하고 이것은 나중에 풀겠습니다
댓글이 비밀댓글로 되어서 다시 업로드했습니다./resources/comment/2020/07/cd7d997b4b78f518fd3e21b3b1d38503.pdf
안녕하세요!
열심히 풀이를 작성해 줘서 고마워요! 그런데 풀이에서 정의한 연결수가 어떤 것인지 명확히 이해되지 않아요.
다시 작성해주면 좋을 것 같아요~!
4. 트리 T의 크기가 N 이라고 하겠습니다.
우선 트리 T를 포함하지 않는 그래프의 채색수는 N - 1 이하임을 보이겠습니다.
채색수가 N 인 그래프 G를 생각해봅시다.
이 그래프를 N개의 색을 사용하여 임의로 채색한 그래프가 주어졌다고 합시다. 편의상 색에 번호를 주어 1, 2, ..., N 번째 색이라고 표현할 것입니다.
이 그래프의 모든 노드에 대해서 다음을 반복합니다.
* 자신과 이웃하는 노드들 중에 자신의 색보다 큰 어떤 색이 없다면 자신의 색을 그 색으로 바꾼다.
모든 노드의 색 번호가 무한이 증가할 수 없으므로 위의 알고리즘은 언젠가 종료할 것입니다.
알고리즘이 종료한 뒤에 모든 노드는 자신보다 번호가 큰 색과 적어도 하나씩 연결되어 있을 것입니다.
또한, 채색수가 N이므로 이 알고리즘을 시행한 후에도 1~N번 색을 가진노드들이 적어도 하나씩 존재할 것입니다.
이제 트리 T에서 DFS 를 수행하면서 노드에 방문 순서에 따라 번호를 매깁니다.
비어있는 정점집합 V, 비어있는 간선집합 E, 비어있는 큐 Q가 주어지면 G에서 색이 1인 임의의 노드 v를 Q에 넣고 다음 시행을 반복합니다.
* 큐에서 front 에 있는 노드 u를 꺼냅니다. u를 V에 넣습니다.
* u의 색과 같은 방문순서를 가진 T의 노드 u' 의 자식들의 방문순서들을 {
} 라고 합시다.
* G 에서 u와 연결되어 있으면서 색이 {} 인 노드들을 큐에 삽입합니다. 동시에 간선 
를 E에 넣습니다.
위의 알고리즘이 종료되었을 때, T'=(V,E) 를 생각하면, G의 부분집합이면서 T와 동일한 트리일 것이므로 채색수가 N 이상인 그래프는 무조건 크기 N인 트리 T를 포함하는 것을 알 수 있습니다.
따라서, 크기 N인 트리 T를 포함하지 않는 그래프의 채색수는 N - 1 이하라고 말할 수 있습니다.
한편, 
을 생각하면 크기 N인 트리 T를 포함하지 않는 채색수가 N - 1 인 그래프이므로
의 최솟값은 N - 1 입니다.
폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.
☎문의 02-6749-3911
정기구독 인증방법 안내
