수학동아 - 폴리매스

폴리매스 문제

세상에 없던 문제에 도전하세요!

[대한수학회] 대60. 그래프의 가까운 변들의 모임

수학동아 2021.12.03 08:54 조회 610

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

대한수학회 60번

그래프의 가까운 변들의 모임

문제 출제자 : 김린기 인하대학교 수학과 교수

그래프에서 서로 다른 두 변이 한 점을 공유하거나 두 변을 연결하는 변이 존재할 경우, “두 변은 가깝다”라고 한다. 아래 그래프에서 $e_{1}$ 과 $e_{4}$ 는 한 꼭짓점을 공유하므로 둘은 가깝다. $e_{1}$ 과 $e_{2}$ 는 꼭짓점을 공유하지는 않지만 $e_{4}$ 가 두 변을 연결하므로 $e_{1}$ 과 $e_{2}$ 도 가깝다. 하지만 $e_{1}$ 과 $e_{3}$ 는 가깝지 않다.

그래프 $G\mathit{}$ 의 변으로 구성된 집합 $S\mathit{}$ 에 대하여, $S\mathit{}$ 의 임의의 두 변이 서로 가까우면 $S\mathit{}$ 를 “가까운 변의 집합”이라 하자. 위의 그래프에서 $\left \{ e_{1},e_{2},e_{4},e_{6} \right \}$ 와 $\left \{ e_{4},e_{5},e_{6},e_{7} \right \}$ 는 가까운 변의 집합이다. 그리고 그래프 $G\mathit{}$ 의 가까운 변의 집합 중 가장 큰 것의 크기를 $\omega (G)$ 로 표기하자.

문제1. $C_{n}$ 은 길이가 $n\mathit{}$ 인 순환그래프(cycle)이다. 정의에 의하면 $\omega (C_{3})=3, \omega (C_{4})=4$ 라는 것을 쉽게 알 수 있다. 5 이상인 자연수 $n\mathit{}$ 에 대하여 $\omega (C_{n})$ 을 구하여라.

문제2. 임의의 짝수 $n\mathit{}$ 에 대하여 $\Delta (G)=n extit{}$ 이고 $\omega (G)=\frac{5}{4}\mathit{\Delta (G)^{2}}$ 인 그래프 가 존재할까? ( $\Delta (G)$ 는 $G\mathit{}$ 의 최고 차수이다.)

문제3. 그래프 $G\mathit{}$ 는 $E(G)$ 가 가까운 변의 집합을 이루는 그래프이다.(여기서 $E(G)$ 는 $G\mathit{}$ 의 모든 변을 포함하는 집합이다.) 즉, $G\mathit{}$ 의 임의의 두 변은 한 꼭짓점을 공유하거나, 둘을 연결하는 다른 변이 존재한다. 예를 들어, $C_{3}, C_{4}, C_{5}$ 는 위의 성질을 만족한다.

이때 $\left | E(G) \right |=\omega (G)\leq \frac{5}{4}\mathit{\Delta (G)^{2}}$ 을 증명하여라.

문제4. 이분그래프 $G\mathit{}$ 에 대하여 $\mathit{\omega (G)\leq \Delta (G)^{2}}$ 임을 증명하여라.

태그

#그래프 #김린기 #인하대학교

이전글 대59. 그래프와 연결 부분그래프의 성질

다음글 대61. 원과 다각형

문제 찜하기 목록보기

댓글 작성하기

222 Lv.9 2021.12.04 11:17

1번에서 제가 잘못 이해한 것 같은데 $w(C_{5})=5$ 이고 $w(C_{6})$ 부터는 계속 3이 되는 것 같은데 설명해주실 수 있나요? 인접한 세 변만이 $S$ 가 되서... (죄송해요 제가 그래프 이론을 모릅니다)

(글고 애초에 순환그래프를 몰라서 위키피디아에 쳐봤더니 정다각형 그래프라던데 맞나요?)

댓글 작성하기 좋아요1 댓글수2
- 김다인(멘토) Lv.15 2021.12.09 16:23
  
  어느 부분에서 문제를 잘못 이해했다고 생각하셨는지 더 말씀해주실 수 있나요? 5 이상의 n에 대하여 $w(C_n)$ 을 구하는 것이 문제입니다!
  
  그리고 순환그래프는 정다각형 그래프가 맞습니다! 다른 질문 있으시면 댓글 부탁드릴게요^^
  
  다인 멘토 드림
  
  좋아요1
- Scubed Lv.6 2021.12.31 18:58
  
  저는 5이상에서도 계속 5가 나오는데요..?
  
  그니까 육각형을 예로 들자면 한 변으로부터 인접한 두 변과 그 변과 연결되어있는 두 변, 총 5개인 것 같아요
  
  좋아요0

정기구독 신청

정기구독 회원인증

인증방법 안내

마이정보

닫기

지금 바로
로그인해보세요

로그인 하기

로그인 하면 내가 찜한 문제와 수행 평가를 한곳에서 볼 수 있어요!

㈜동아사이언스 | 등록번호 : 서울 아04396 | 등록일자 : 2017년 3월 2일 | 제호 : 동아사이언스 | 발행인 : 장경애 | 편집인 : 박근태
㈜동아사이언스 폴리매스 | 대표 : 장경애 | 개인정보관리책임자 : 김수희(privacy@dongascience.com) | 청소년보호책임자 : 조기견
서울시 용산구 청파로 109, 7층 (04370) ｜ 문의 : 02-6749-2000 ｜팩스 : 02-3148-0809 ｜사업자등록번호 : 101-81-62201 (사업자정보확인)
통신판매업신고번호 : 제2013-서울용산-01101호 ｜온라인 결제를 위한 PG사의 구매안전서비스(가입사실 확인)

폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.
☎문의 02-6749-3911