이번에도 그래프이론(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.
connected graph 에서 가장 긴 길이를 갖는 path P와 Q는 공통된 점을 갖는다라는 말인데요. 같은 점 하나를 꼭 지난다는 얘기입니다. 이번 글에서 이것의 풀이 방법을 알아보도록 하겠습니다.
그래프이론 관련 글
- [그래프이론 문제풀이] 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) 문제풀이
다시한번 문제를 써보겠습니다.
Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
저는 귀류법을 이용해서 문제를 풀이하도록 하겠습니다. path P와 Q가 공통된 vertex를 갖지 않는다고 가정해보겠습니다. 그리고 P는 v_0-v_1-...-v_n라 표시하고 Q는 u_0-u_1-...-u_n라고 표시하겠습니다. 그래프 G는 connected 이므로 v_0와 u_0를 잇는 path R이 존재합니다. 이 path R을 u_0 - w_1 -w_2-...-w_K - v_0라 표시하겠습니다. R상에서 u_0와 인접한 vertex w_1을 관찰해보겠습니다. Q 는 maximum length를 갖는 path이므로 w_1은 P를 구성하는 vertex인 u_1,u_2,..,u_n중 하나가 되어야 합니다. 안 그러면 P가 더 길어질 수 있기 때문입니다. 따라서 w_1 = u_{i_1}이라고 합시다. 그리고 비슷하게 w_K또한 P를 구성하는 vertex중 하나가 되어야 합니다. w_K = v_{i_2}라고 표시합니다. 그러면 u_0와 v_0를 잇는 path는 u_0-u_{i_1} - w_2 - w_3 -... - v_{i_2}-v_0형태로 표시됩니다. 여기서 i_1 \geq i_2 라면 u_0 - u_1 -u_2 -...-u_{i_1} - w_2 - w_3 ... - w_{K-1} v_{i_2}-v_0라는 P와 Q보다 길이간 긴 path 가 만들어집니다. i_1 < i_2 이어도 비슷하게 P와 Q보다 길이간 긴 path 가 만들어집니다. 따라서 이는 P와 Q가 maximum length를 갖는 path라는 사실에 모순입니다. 따라서 P와 Q는 common vertex를 가져야 합니다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 2의 Homework Problems 중 (1) 문제