그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “Use Menger’s Theorem (κ(x, y) = λ(x, y) when xy /∈ E(G)) to prove that α′(G) = β(G) when G is bipartite.” 이다.
그래프이론 (Graph Theory) 문제풀이
이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.
Use Menger’s Theorem (κ(x, y) = λ(x, y) when xy /∈ E(G)) to prove that α′(G) = β(G) when G is bipartite.
(풀이) G 를 X,Y bipartite graph 라고 하자.
이제 G 에 두개의 vertex u,v 추가한 후, G 를 H 라는 그래프로 확장할 것이다.
확장하는 방식은 아래와 같다.
V(H) = V(G) \cup \{ u, v \} 라 하고 E(H) = E(G) \cup \{ ux | x \in X \} \cup \{ vy | y \in Y \} 라 하자.
M 을 G 위에서 maximum matching 이라 하자.
x_1y_1,x_2y_2,...,x_{|M|}y_{|M|} 를 M 을 구성하는 모든 edge라고 하자. 여기서 x_i \in X , y_i \in Y 이다.
edge들 x_iy_i 로 부터 |M| 개의 internally disjoint uv-path u-x_i-y_i-v 라 만들어진다.
따라서 \alpha^\prime(G) \leq \lambda_H(u,v) 이다.
M 가 maximum matching 이기 위해서는 \alpha^\prime(G) = \lambda_H(u,v) 이어야만 한다.
S 를 H 안에서 uv-separator라고 하자.
G-S 는 X로 부터 Y 로 가는 edge를 갖고 있지 않는다.
따라서 S 는 G 위에서 vertex cover이다.
그러므로 \kappa_H (u,v) \geq \beta(G) 이다.
Menger’s theorem 에 의해 \beta(G) \leq \kappa_H(u,v) = \lambda_H(u,v) \leq \alpha^\prime(G) 이다.
\alpha^\prime(G) \leq \beta(G) 이므로 \alpha^\prime(G) = \beta(G) 이다.
[그래프이론 (Graph Theory) 문제풀이] Determine κ and κ′ for each graph below.
[그래프이론 (Graph Theory) 문제풀이] For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 6 문제