본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대60. 그래프의 가까운 변들의 모임
수학동아 2021.12.03 08:54 조회 2296

 

대한수학회 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 댓글수7
    •  
      김다인(멘토) Lv.15 2021.12.09 16:23

      어느 부분에서 문제를 잘못 이해했다고 생각하셨는지 더 말씀해주실 수 있나요? 5 이상의 n에 대하여 w(C_n)을 구하는 것이 문제입니다!

       

      그리고 순환그래프는 정다각형 그래프가 맞습니다! 다른 질문 있으시면 댓글 부탁드릴게요^^

       

      다인 멘토 드림

      좋아요1
    •  
      Scubed Lv.7 2021.12.31 18:58

      저는 5이상에서도 계속 5가 나오는데요..?

      그니까 육각형을 예로 들자면 한 변으로부터 인접한 두 변과 그 변과 연결되어있는 두 변, 총 5개인 것 같아요

      좋아요0
    •  
      진리를 찾아서 Lv.5 2022.01.31 18:50

      5일 때는 5 맞고 6이상일 때는 임의의 두 원소에 대해서 거리가 2 이상이면 안 되므로 3 맞는듯요.

      좋아요0
    •  
      진리를 찾아서 Lv.5 2022.01.31 18:51

      6 이상일 때 w(Cn) 값이 4 이상이면 반드시 거리가 2 이상인 두 변이 생기거든요.

      좋아요0
    •  
      222 Lv.9 2022.01.31 19:14

      @Scubed

      정육각형을 예로 들자면

      서로 마주보는 면은 가까운 면이 아니니

      기껏해야 한 면 + 꼭짓점으로 맞닿아 있는 두 면 해서 w(C_6)이 3이 나오는 것 같습니다

      좋아요0
    •  
      진리를 찾아서 Lv.5 2022.01.31 20:38

      좀 더 엄밀하게 이야기해 보겠습니다.

      n = 5일 때는 C5 전체가 가까운 변의 집합이므로 답은 5입니다.

      n >= 6일 때 연속한 3개를 잡아보면 이는 가까운 변의 집합입니다. 이것이 최댓값임을 보이기 위해 w(Cn)의 값이 4 이상인 집합 S가 존재한다고 가정해봅시다. 고립된 변이 있으면 가까운 변의 집합일 수 없으며, Cn은 정다각형 그래프이므로 집합 S는 일직선 형태일 것입니다. 이때, 집합 S의 모든 변을 일직선 순서대로 E1, E2, E3, E4, ...라고 합시다.

      E1, E4의 거리는 두 방향에서 잴 수 있는데, 그 길이는 2와 n-4입니다. 그런데 이 두 수는 모두 2 이상이므로 가까운 변의 집합이 될 수 없습니다. 따라서 w(Cn)의 값은 4 이상일 수 없으며, 답은 3입니다.

      답 : n = 5이면 5, n >= 6이면 3

      좋아요0
    •  
      Scubed Lv.7 2022.02.02 15:07

      @222

      고렇네요 제가 실수했네요 ㅠㅠ

      좋아요0
  •  
    immanuel Lv.1 2022.01.31 14:21

    혹시 이런 문제를 취미로 풀어보고 싶다면 어떻게 공부해야할까요ㅠㅠ 수능이나 내신대비를 위한 수학만 해서 이런 수학문제를 푸는 것에는 익숙하지 않은데 이런 문제를 해결하는 것을 공부할 수 있는 책이 있을까요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      Scubed Lv.7 2022.02.02 15:07

      책은 저는 딱히 못 봤고 그냥 이런 문제들을 계속 풀어볼려고 노력하면서 좀 더 가까워진 거 같아요

      좋아요0
  •  
    진리를 찾아서 Lv.5 2022.02.04 10:08

    2번에서 별 정보는 아니지만 n = 2일 때는 C5가 조건을 만족하네요.

    댓글 작성하기 좋아요0 댓글수0
  •  
    pure math Lv.7 2022.02.08 11:50

    최고 차수라는 것이 무슨 뜻인가요? 최대 집합의 개수인가요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      진리를 찾아서 Lv.5 2022.02.08 16:52

      그래프에서 한 점에 연결된 변의 수를 차수라고 하는데, 모든 점에 대해서 가장 높은 차수를 최고차수라고 합니다.

      예시로 문제에 나와있는 그래프에서는 차수는 2,2,2,2,3,3이고 최고차수는 3이 되겠지요.

      좋아요0
    •  
      pure math Lv.7 2022.02.08 17:14

      으아닛! 감사합니다! 이미 진리를 찾아서님은 진리를 찾으신 것 같군요!

      좋아요0
  •  
    부분해결
    pure math Lv.7 2022.02.08 12:04

    1)

    최대한 정리해서 말하겠습니다.

    정다각형 그래프에서, w(C5)는 5이고, 그 뒤는 모두 3입니다.

    우선, 최대인 점들이 존재할려면, 한점에 대해서 그 점에서 한쪽으로는 2개의 점만이 퍼져나가야합니다. 모두 가까워야 되기 때문이지요.

    반대도 같고, 그래서 한 점에서 양끝으로 2개가 있는 것이 최대입니다. 하지만, 모든 점에서 가까워야 하므로, 양끝도 가까워야 합니다. 그래서, 양끝을 이어주면 최대인 5가 됩니다.

    정다각형 모양을 가진 최대는 5인 것이죠.

    그러면, 6이상부터는 이것이 성립하지 않고, w(G)는 직선형이 되면서, 최대가 3이 됩니다.

    w(C5)=5, w(C6이상))=3 입니다.

     

    댓글 작성하기 좋아요0 댓글수2
    •  
      조영준 멘토 Lv.3 2022.02.09 16:56

      잘 풀었습니다!

      좋아요0
    •  
      pure math Lv.7 2022.02.09 17:39

      우아아ㅏ아아아아아ㅏ아아아아아아아ㅏ아아아아아아

      대한수학회 문제푼거 첨이에요!!!

      감사합니다 멘토님!!

      좋아요0
  •  
    pure math Lv.7 2022.02.08 17:58

    아 그리고 w(G)=5/4뭐시기(G)2인데 집합G를 제곱한건가요 아니면 n을 제곱한건가요??

    댓글 작성하기 좋아요0 댓글수4
    •  
      진리를 찾아서 Lv.5 2022.02.08 18:37

      제 생각에는 아마 n을 제곱하라는 것 같습니다. 왜냐하면 그래프를 제곱한다는 말은..들어본 적이 없거든요.

      좋아요0
    •  
      pure math Lv.7 2022.02.08 18:51

      오오 그럼 저 이 문제에대해서 감 잡았는데 이 문제에 대하여 같이 토론하고 풀어보실래요??

      좋아요0
    •  
      진리를 찾아서 Lv.5 2022.02.08 20:23

      오 그럽시다

      좋아요0
    •  
      pure math Lv.7 2022.02.08 20:26

      오 밑에 새로운 댓글 달았어요 거기서 한번 이 문제 자체를 같이 푸러봅시다

      좋아요0
  •  
    pure math Lv.7 2022.02.08 20:26

    2번 문제에 대해서, 일반적인 방법을 찾는것이 좋을까요 아니면 수식적으로 증명하는 것이 나을까요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      pure math Lv.7 2022.02.08 21:00

      +추가로 이 문제는 한붓그리기와 연관이 있는 것 같습니다. 확실합니다!

      @진리를 찾아서

      좋아요0
  •  
    pure math Lv.7 2022.02.08 22:45

    어? 이거 4색정리 증명할때 나오는 것과 비슷한데 이거 4색정리와도 관련성이 깊은 것 같습니다

    댓글 작성하기 좋아요0 댓글수0
  •  
    asdf3 Lv.4 2022.02.10 17:30

    2번에서 n=4일 때 그래프가 존재합니다. 

    댓글 작성하기 좋아요0 댓글수0
  •  
    부분해결
    진리를 찾아서 Lv.5 2022.02.11 00:05

    풀었습니다. (p.s. pure math님 같이 토론하기로 하고 못해서 죄송합니다ㅠㅠ 숙제가 많아서 가끔씩 눈팅밖에 못했어요)(p.s2 asdf3님 감사합니다 님이 n = 4일 때를 보여주셔서 일반화할 수 있었습니다)

    /resources/comment/2022/02/d87d4ae8734db269b92c018c31171af4.jpg

    댓글 작성하기 좋아요0 댓글수3
    •  
      유태영 멘토 Lv.3 2022.02.23 10:57

      잘 푸셨습니다.

      다음과 같은 방법으로 서술할 수도 있습니다.

      let n = 2m

      다음과 같은 그래프 G를 잡자.

      V(G)={(a,b) : 1 <= a <= m, 1<= b <= 5}

      E(G)={{(a,b),(c,d)} : b-d가 mod5로 1 or -1}

      let f(v) = v의 두 번째 index in mod5.

      각각의 점은 f(v)값이 1 차이나는 점과 연결되고 차수 2n.

      한편, {v1,v2}, {v3,v4}가 이웃하지 않다면 v1,v2는 v3,v4와 연결되지 않고 일반성을 잃지 않고 f(v1)=0, f(v2)=1일 때, f(v3)=f(v4)=3이고 모순.

      따라서 모든 변이 이웃하고 w(G)=|E(G)|=5m^2

       

      좋아요0
    •  
      pure math Lv.7 2022.02.26 11:42

      와!!! 축하드려요!!! 다음엔 시간 날 때 같이 문제 풀어봐요!!!

      좋아요0
    •  
      진리를 찾아서 Lv.5 2022.02.26 12:29

      유태영 멘토님, pure math님 모두 감사합니다!

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

  • ☎문의 02-6749-3911