그래프이론 문제풀이를 하려고 한다. 내가 풀려고 하는 문제는 아래와 같다.
그래프이론 문제내용
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.
Simple graph 가 있고 그 중에 하나의 edge uv가 있다고 하자. edge는 삼각형의 구성요소 일 수도 있고 아닐 수도 있다. 이 때 edge를 한변으로 갖는 삼각형의 갯수가 적어도 d(u) + d(v) − n(G) 개 라는 의미이다.
도움이 될만한 글과 영상
그래프이론 문제 풀이 내용
어떻게 하면 풀수 있을까? 삼각형을 만들려면 세개의 변이 존재해야 한다. edge uv 가 존재하는 것은 문제에 주어져 있다. 남은 두변은 어떻게 만들까? vertex u와 vertex v가 공통으로 adjacent 한 vertex의 갯수를 세면 된다. 먼저 u의 neighbor 를 생각하자. u와 adjacent한 vertex를 생각해보자라는 얘기이다. v를 제외하고 u와 adjacent 한 vertex의 갯수는 degree의 정의에 의해 d(u)-1 이다. 비슷하게 u를 제외하고 v와 adjacent vertex의 갯수는 d(v)-1 이다.
d(u)-1: v를 제외한 u와 adjacent한 vertex갯수
d(v)-1: u를 제외한 v와 adjacent한 vertex갯수
이제 이 d(u)-1개의 vertex와 d(v)-1개의 vertex중 겹치는 vertex를 찾으면 된다. 그러기 위해서는 먼저 v를 제외하고 u와 adjacent 한 vertex의 수 d(u)-1개를 센다. 그리고 u를 제외하고 v와 adjacent한 vertex의 수 d(v)-1개를 센다. d(u)-1+d(v)-1 에서 n(G)-2 를 빼면 된다. n(G)-2는 G의 vertex중 u와 v를 제외한 vertex의 총 갯수를 의미한다. 왜 n(G)-2를 빼면 되는지는 독자분들께서 생각해보자. 이제 작전을 세웠으니 경우를 나눠서 실행해 보자.
첫번째) d(u)+d(v)-n(G) ≤0 인 경우
이럴 때는 구지 계산할 필요가 없다.
두번째) d(u)+d(v)-n(G) >0 인 경우
앞에서 설명했듯 u를 제외하고 v와 adjacent한 vertex의 갯수와 v를 제외하고 u와 adjacent한 vertex의 갯수를 더해주고 n(G)-2를 빼면 u와 v에 동시에 adjacent한 vertex의 갯수를 셀 수 있다.
위의 사실을 종합하면 uv가 속하는 삼각형의 갯수는 최소 d(u)+d(v)-n(G)개임을 알 수 있다. 사실 이문제를 풀면서 삼각형이 안나올 수 있는 최악의 가정을 해놓고 문제를 풀었다. 그래프이론에서 많이 사용되는 argument이므로 익혀두면 좋겠다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 2의 Warm-up Problems 첫번째 문항