그래프이론(Graph Theory)문제풀이입니다. 이번에 풀어볼 문제는 “For every graph G, prove that β(G) ≤ 2α'(G). For each k ∈ N, construct a simple graph G with α'(G) = k and β(G) = 2k.” 입니다.
그래프이론(Graph Theory)문제풀이
이번에 풀 문제는 아래와 같습니다.
For every graph G, prove that β(G) ≤ 2α'(G). For each k ∈ N, construct a simple graph G with α'(G) = k and β(G) = 2k.
풀이) G를 connected graph라고 가정해도 된다. M 을 그래프 G의 maximum matching 이라고 하자. v_1,v_2,..v_N 를 maximum matching 을 구성하는 edge들의 vertices라고 하자. 그러면 N/2 = M 이다. 이제 H=G-\{v_1,v_2,...,v_N\} 라고 하자. w_1 w_2 \in E[H] 라 하자. 그러면 w_1w_2 는 v_i 를 endpoint로 하는 edge와 만나지 않는다. 따라서 M \cup w_1w_2 은 matching 이 된다. M은 maximum matching 이었기 때문에 결론적으로 E[H] = \empty 이다. 따라서, v_1,v_2,..,v_N 는 vertex cover가 되고 그러므로!
\beta(G) \leq N =2M = \alpha\prime(G)그리고, disjoint 한 삼각형 k개로 구성된 그래프 G에 대해 \alpha \prime(G) =k, \beta(G) = 2k
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 5 문제