저희 학교에서 12개의 그룹, 즉 a,b,c,d,e,f,g,h,i,j,k,l 그룹이 있는데 2그룹씩 짝을 지어 6개의 짝을 만들어야 합니다. 'a-b, c-d, e-f,g-h,i-j,k-l' 이런식으로요. 그런데 단순히 이렇게 한번만 만들고 끝나는 것이 아니라 모든 그룹이 서로 한번씩 짝이 될 때까지, 이미 만났던 짝은 만나지 않으면서 6개의 짝을 만드는 과정을 계속 반복하고자 합니다.
질문은,
1. 이게 가능한 것인가요?
2. 가능하다면 어떻게 해야 하는지요?
수학갤러리의 현자분들께 미리 감사인사 드립니다.
조합론은 개판인 사람으로서, 10분동안 간략하게 풀어봤는데 불가능할 것이라 추정됨.
해봤는데 잘 안 되넹
이게 어려운 이유가 너무 불가능해서 오히려 헷갈려서 그런 거 아니었을까...?
이거 돼
일단 4개 일때 해보고 그거를 12개 일때에 적용해보면 6그룹을 각각 두개씩 짝찌어서 쭉 해나갈수 있는 것 같음 다시 체크해볼게
12개의 vertex를 가진 complete graph가 edge chromatic number (chromatic index)가 11임을 증명하면 됨.
설명 : 그래프 G에 대해서 edge coloring은 vertex를 공유하는 edge끼리는 다른 색을 가지도록할때 필요한 최소 색의 수를 의미함. 결국 문제에서 요구하는건 12개의 vertex를 가진 완전그래프 (i.e. 임의의 두 vertex 사이에 edge가 있는 그래프) 의 edge들이 edge disjoint한 perfect matching (모든 vertex를 포함하면서, 임의의 두 edge가 vertex를 공유하지 않는 subgraph) 들로 덮을수 있는지 묻는 것이고, 이는 정확히 edge chromatic number가 11인지 묻는 것과 같음.
Vizing theorem은 임의의 그래프 G에 대해서 edge chromatic number가 G의 maximum degree + 1 이하라는 정리인데, edge chromatic number는 정의로부터 적어도 maximum degree만큼 필요하기 때문에, 정점 n개짜리 완전그래프 K_n은 edge chromatic number가 n -1또는 n임. n이 홀수라면 perfect matching이 존재할수 없으므로 K_n의 edge chromatic number가 적어도 n 이상이므로 정확히 n이 되고, n이 짝수라면 K_n의 edge chromatic number가 n-1임을 수학적 귀납법을 이용해서 증명할 수 있음.
ㄴ 헐 형님 개쩌네영 이런거 공부할라면 무슨 책봐야해여?
https://math.stackexchange.com/questions/1172005/chromatic-index-of-a-complete-graph 이 게시물의 첫번째 답변을 보면 n이 홀수일때 K_n의 edge coloring이 주어졌을때 K_{n+1}의 색 n개짜리 edge coloring을 explciit하게 만드는 방법이 있음.
본문의 문제는 실제로 그래프 뿐만 아니라 r-uniform hypergraph에 대해서 확장된 결과가 있는데, Baranyai의 정리라고 함. https://en.wikipedia.org/wiki/Baranyai's_theorem 본문의 내용은 r=2 (그래프) 인 경우. 본문에서 정점개수가 12개이므로 Baranyai's theorem의 조건 (n이 r로 나누어떨어진다는것) 을 만족하므로 본문에서 요구한 내용이 성립함.
세상에
띠용
123갑 ㅁㅊㄷㅁㅊㅇ
@.@ 답변들이 전혀 이해가 안 되는데, 그래서 가능한가요 불가능한가요?
Baranyai's theorem의 증명은 Van Lint의 교재 a course in combinatorics 교재의 한 챕터로 구성되어있으니 그걸 참고하면 되지만 일반적인 r-uniform hypergraph인 경우의 증명이라서 본문의 r=2인 경우 (그래프) 는 그냥 Vizing theorem과 위 stackexchange 링크에 걸린 construction에 의해서 성립함.
정리하자면 본 글에서 묻는게 12개의 그룹이 있고 매 시행마다 2개씩 짝지어서 기존에 형성된 짝과 겹치지 않는 6개의 짝을 만들때, 모든 나올수 있는 12C2 = 66가지의 pair가 총 11번의 시행을 거쳐서 모두 나타나는것을 묻는것 같은데, 이 문제는 정점 12개로 이루어진 완전그래프의 chromatic index가 11개냐? 라고 묻는것과 같은 질문이고, 일반적으로 정점 2n개로 이루어진 완전그래프의 chromatic index는 2n-1이라는 사실을 증명할 수 있어서 참이에요.
123님의 말을 1줄요약하면 된대 - dc App
가능하다면 간단하게 실제로 조합만드는 방법을 알 수 있을까요? ㅠㅠ
저 위의 stackexchange 링크의 첫번째 답글에 구체적인 edge coloring이 명시되어있습니다.
12개의 정점을 {0,1,2,..,11}이라 한다면, 먼저 0<=i<j<=10에 대해서 edge {i,j}을 i+j (mod 11)로 칠합니다. 그리고 0<=i<=10에 대해서 edge {i,11}을 2i (mod 11)로 칠합니다. 이것이 edge coloring의 조건을 만족한다는건 쉽게 확인할 수 있습니다. 이제 0<=i<=10에 대해서 색깔 i로 칠해진 edge들의 양 끝점이 i번째 시행에서의 짝들을 의미합니다.
조합폭격보솤ㅋㅋㅋ
와 씨발 지렸다
조합론도 진짜 흥미로운 주제같긴 한데...그 주제가 어느정도 학습하지 않으면 의미있는 결과가 안나오는 모래시계 형태라서 그냥 벽처럼 보임 ㅠㅠ
그냥 이거 고등학교때 배웠던걸로 하니까 되는거같은데 위에 설명은 영어가 많아서 무슨소린지 1도모르겠당... 헤헷!!
띠용