[그래프이론(Graph Theory) 문제풀이] Prove or disprove: K9 decomposes into copies of C9.

그래프이론(Graph Theory) 문제를 풀이하겠습니다. 오늘 만나볼 문제는 아래와 같습니다.

Prove or disprove: K9 decomposes into copies of C9.

완전 그래프 K9이 C9에 의해 분해가 되는지 물어보고 있습니다. 이번 글에서는 C9에 의해 분해가 되는지 안되는지 살펴보겠습니다.

참고할만한 글:

• [그래프이론(Graph Theory)] Use induction to prove that if a graph does not have an odd cycle then it is bipartite.
• [그래프이론(Grpah Theory)] Prove that the Petersen graph has no cycle of length 7.
• [그래프이론(Graph Theory) 문제풀이] Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
• [그래프이론(Graph Theory) 문제풀이]Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
• [그래프이론 문제풀이] Let u and v be adjacent vertices in a simple graph G. Prove that uv belongs to at least d(u) + d(v) − n(G) triangles in G.
• [그래프 이론(Graph Theory)-1] k-set과 k-subset

그래프이론(Graph Theory) 문제풀이 실패

댓글에서 지적하신 바와 같이 확인 결과 이 문제풀이 방법은 틀렸습니다.

댓글에서 지적하신 바와 같이 확인 결과 이 문제풀이 방법은 틀렸습니다.

풀고자 하는 문제를 한번 더 recap해보겠습니다. 문제는 아래와 같습니다.

Prove or disprove: K9 decomposes into copies of C9.

풀이:

아래와 같이 vertex를 나열해두고. cycle을 만들어보겠습니다.

 

이제 이 vertex들을 이어 cycle을 만듭니다.

 

이제 두번째 Cycle을 만들기 위해 아래처럼 처음 만들었던 vertex의 배열에 +1 mod 9를 해줍니다. 그리고 cycle을 만들어줍니다.

이런식으로 +1 mod 9를 해서 서로다른 cycle 4개를 만들 수 있습니다. 문제풀이 결과 얻어내는 cycle은 아래와 같이 네개가 있습니다.

• 1-2-9-3-8-4-7-5-6-1
• 2-3-1-4-9-5-8-6-7-2
• 3-4-2-5-1-6-9-7-8-3
• 4-5-3-6-2-7-1-8-9-4

댓글에서 지적하신 바와 같이 확인 결과 이 문제풀이 방법은 틀렸습니다.

댓글에서 지적하신 바와 같이 확인 결과 이 문제풀이 방법은 틀렸습니다.

그래프이론 (Graph Theory) 문제 풀이 성공

Prove or disprove: K9 decomposes into copies of C9.

처음에 푼 방식이 틀렸어서 고민을 하니까 문제가 풀리더군요. 규칙은 발견하지 못했습니다만 답은 찾았습니다.

1-2-9-3-8-4-7-5-6-1

2-3-1-4-9-5-8-6-7-2

3-4-2-5-1-7-8-9-6-3

4-5-3-7-9-1-8-2-6-4