본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대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}}임을 증명하여라.

 

 

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

  • ☎문의 02-6749-3911