본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬17. 그래프의 삼각형
수학동아 2021.09.08 11:21 조회 207

n은 임의의 자연수다. 어떤 그래프의 서로 다른 세 점이 두 쌍씩 모두 변으로 이어져 있으면, 이 세 점의 집합을 이 그래프의 삼각형이라고 하자.

 

문제 1.

2n개 꼭짓점으로 이루어진 그래프가 삼각형이 하나도 없다면, 이 그래프는 최대 몇개의 변을 가질 수 있을까? 

 

문제 2.

문제 1에서 얻은 삼각형을 피하는 최대 변 개수에 변을 딱 하나 더 추가하면, 삼각형이 무조건 하나는 생겨야 한다. 과연 삼각형은 최소 몇개가 더 생길까?

 

 

힌트 :  이 문제는 Turan's theorem 또는 Mantel's theorem으로 알려진 내용이다. 먼저 스스로 문제에 대해 충분히 고민해보고, 그 다음에 관련 자료를 구글링 등을 통해 찾아 공부해보자. 배운 내용을 친구들에게 설명하는 것도 좋다!

  •  
    Scubed Lv.6 2021.09.08 20:35

    이건 좀 쉬울 것 같다고 생각되는 느낌이 있을 수도...

    함 풀어봐아징

    댓글 작성하기 좋아요0 댓글수0
  •  
    Scubed Lv.6 2021.09.11 00:19

    아이디어) 그래프에서 삼각형이 생기면 안되니 두 변이 있을 때는 나머지 하나를 다른 색으로 이으면 안될까요?

    ex)

    댓글 작성하기 좋아요0 댓글수1
    •  
      Scubed Lv.6 2021.09.11 00:19

      파랑이 이으면 안되는 선분입니다

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

  • ☎문의 02-6749-3911