[그래프이론 (Graph Theory)] For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.

그래프이론(Graph Theory) 문제풀이 하겠습니다. 이번에 풀어볼 문제는 “For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.” 입니다.




그래프이론(Graph Theory) 문제풀이

For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.

풀이)

우선은 n=16이고 1-factor가 없는 3-regular simple graph 를 아래와 같이 만들 수 있다.

스크린샷 2023 10 15 013207
그림1. n=16 이고 1-facotr가 없는 3-regular graph

이제 vertex를 두개씩 추가해서 vertex 갯수 n=18,20,22… 인 simple graph 만들것이다. vertex를 추가하는 방법에 대해서는 아래 그림에 표현하였다.

스크린샷 2023 10 15 013221
그림2. 기존 vertex degree안건들이고 degree 3자리 vertex 두개 추가 과정

위의 그림처럼 한다면 기존 vertex의 degree를 건들이지 않고 degree가 3인 두개의 vertex를 추가할 수 있다. 이 방법을 그림1.에 적용하여 아래와 같이 n이 16이상인 짝수일 때 3-regular graph 를 만들 수 있다.

스크린샷 2023 10 15 013230
그림3. 짝수 n이 16 이상 일 때 1-factor 존재 안하는 3-regular simple graph

위의 그림3.의 그래프에서 1-factor를 만들기 위해서 edge e1,e2,e3중에 e2를 택했다고 하자. 그러면 이제 G1의 1-factor를 찾아야 겠는데! G1의 vertex갯수는 홀수개이므로 G1의 1-factor를 존재하지 않는다. 따라서 graph에서 1-factor가 존재하지 않는다.

 

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 5 문제

Leave a Comment