그래프이론 (Graph Theory) 문제풀이 하겠다. 풀고자 하는 문제는 “Diameter vs. radius (a) Prove that the distance function d(u, v) on pair of vertices of a graph satisfies the triangle inequality: d(u, v) + d(v, w) ≥ d(u, w) (b) Use part (a) to prove that diam(G) ≤ 2rad(G) for every graph G. (c) For all positive integers r and d that satisfy r ≤ d ≤ 2r, construct a simple graph with radius r and diameter d.” 이다.
그래프이론 (Graph Theory) 문제풀이
Diameter vs. radius
(a) Prove that the distance function d(u, v) on pair of vertices of a graph satisfies the triangle inequality: d(u, v) + d(v, w) ≥ d(u, w)
(b) Use part (a) to prove that diam(G) ≤ 2rad(G) for every graph G.
(c) For all positive integers r and d that satisfy r ≤ d ≤ 2r, construct a simple graph with radius r and diameter d.
풀이)
(a) u,w를 vertex라고 합시다. uw-path P가 d(u,w) 길이를 갖는다고 합시다. 그리고 uv-path Q 가 d(u,v) 길이를 갖는다고 합시다. 그리고 vw-path R 이 d(v,w) 길이를 갖는다고 합시다. Q와 R을 이어서 uw-walk 를 만들고 이 walk로 부터 path T를 만듭니다. 그러면 d(u,w) \leq l(T) \leq d(u,v)+d(v,w) 성립합니다.
(b) d(u,w) \leq d(u,v) + d(v,w) \leq \epsilon(v) + \epsilon(v) = 2\epsilon(v) 이다. 여기에 v 에 대해 최소값을 취하면 d(u,w) \leq d(u,v) + d(v,w) \leq 2 rad(G) 이고 u,w에 최대값을 취하면 아래와 같이 식이 유도됩니다.
diam(G) \leq 2rad(G)
(c) V = \{ 0,1,2,...,2r-1\} 위에 정의된 cycle C_{2r} 에 대해 생각하자. 이 때 rad(C_{2r})=r이다. d=r 인 경우 diam(C_{2r}) = rad(C_{2r}) = r 성립한다. 이제 2r \geq d > r 이라 가정하자. 이제 r \in V 에서 시작하는 길이가 d-r 짜리 path P_{d-r} = r-v_1-v_2....-v_{d-r} 에 대해 생각하자. 이 때 v_i \notin V 이 되도록 설정하였다. G = C_{2r} \cup P_{d-r} 라 하자. 0 부터 v_{d-r} 까지 길이가 d 인 path를 만들 수 있다. 따라서 diam(G) = d 이다. \epsilon_G(v) 를 구하기 위한 path위에는 r 이 있을수 밖에 없으므로 rad(G) = \epsilon_G(r) 이 되고 rad(G) =r 이 된다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 5 문제