본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬12. 전갈 그래프
수학동아 2021.03.31 18:45

그래프 G는 유한한 꼭짓점의 집합 V와, V의 서로 다른 두 점을 잇는 일부 변의 집합 E로 이뤄진 구조다 (자세한 설명은 슬기로운 수학생활 6번을 참고하기 바란다).

욱제는 꼭짓점이 n개인 그래프 G를 숨기고 있다. 각 꼭짓점은 1부터 n까지 번호가 매겨져 있다. 

연두는 욱제의 그래프가 '전갈 그래프'인지 확인하고 싶다. 전갈 그래프는 서로 다른 세 개의 꼭짓점 '독침', '꼬리', '몸통'이 있어서 다음 성질을 만족하는 그래프로 정의한다.

1. 독침은 꼬리에만 연결되어 있다. 2. 꼬리는 몸통과 독침에만 연결되어 있다. 3. 몸통은 독침이 아닌 모든 꼭짓점들과 연결되어 있다. 몸통은 독침과는 연결되어 있지 않다. 4. 독침도, 꼬리도, 몸통도 아닌 꼭짓점들끼리는 서로 연결될 수도 아닐 수도 있다.

전갈 그래프의 예시 

욱제는 그래프를 꽁꽁 숨기고 있어서, 연두는 그래프의 일부 정보만을 질문을 통해 파악할 수 있다. 이때 질문은 "i번 꼭짓점이 j번 꼭짓점과 연결되어 있는가?"의 형태만 가능하고, 욱제는 i번 꼭짓점이 j번 꼭짓점과 연결되어 있는지/아닌지만 답변한다. 예를 들면 다음과 같이 연두와 욱제가 질답을 할 수 있다:

연두: "1번하고 2번"

욱제: "연결되어 있어"

연두: "2번하고 3번"

욱제: "연결되어 있지 않아"

연두: "1번하고 3번"

욱제: "연결되어 있지 않아"

이 질답만으로 연두는 (만약 그래프가 전갈 그래프라면) 3번 꼭짓점이 몸통이 될 수 없음을 알 수 있다. 몸통과 연결되지 않는 다른 꼭짓점의 개수는 정확히 1개지만, 욱제의 그래프에서 3번은 1번하고 2번과 연결되어 있지 않기 때문이다.

연두가 꼭짓점의 갯수 n만 알고 욱제의 그래프를 아예 모르는 상태에서 시작할 때, 연두가 최대 300n개의 질문을 해서 욱제의 그래프가 전갈 그래프인지 아닌지를 확인할 수 있을까?

 

  •  
    통계의끝을본남자 Lv.8 2021.04.01 11:44

    그러면 그냥 몸통,꼬리,독침 이렇게 3개로만 이루어질 수도 있나요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    jeuno Lv.5 2021.04.01 20:34

    지금 당장 생각나는 것은 n-2개의 점이 서로서로 모두 연결되어 있는 전갈 그래프일 때, 연두가 정말정말 운이 좋지 않아서 꼬리와 독침을 제외한 모든 점의 연결상태를 묻고 몸통과 꼬리, 꼬리와 독침, 독침과 몸통을 물었을 때 즉, \binom{n-2}{2}+3=\frac{(n-2)(n-1)}{2}+3이 최악의 경우가 될 것이다. 라는 생각이 드네요. 만약 이것이 맞는 설명이 된다면 최악의 상태만 기준으로 할 때,  \frac{(n-2)(n-1)}{2}+3\leq 300n이어야 그래프를 확인할 수 있을 것이고 이를 만족시키는 n은 (n은 어쨌든 정수니까) n\leq 302, 점이 302개 이하이면 가능하다라고 할 수 있을 것 같네요. 이제 우리가 생각해보아야 할 것은 '질문의 수를 줄이는 전략이 있는가?'가 되겠네요.

    댓글 작성하기 좋아요0 댓글수0
  •  
    통계의끝을본남자 Lv.8 2021.04.01 23:47

    모든 꼭짓점이 서로 이어져있는지 아닌지 알면 되므로 n((n-1)/2가 300n보다 작으면 되니까 n이 601 이하이면 알 수 있을 것 같습니다

    그런데 601 초과인 경우는 모르겠네요...

    댓글 작성하기 좋아요0 댓글수0
  •  
    바람개비 Lv.3 2021.04.04 01:59

    욱제의 그래프가 전갈 그래프라고 가정하여 독침이 될 수 있는 점을 찾고 이를 통해 전갈 그래프인지 판별하는 방법을 생각해 보았습니다.

     

    먼저 임의의 꼭짓점을 잡고, 그 꼭짓점에 연결된 점의 집합 A와 그렇지 않은 점의 집합 B로 나눈 다음 각 집합에서 원소를 하나씩 골라 서로 연결되어 있는지 확인합니다.

    연결되어 있으면 B에서 고른 원소를 빼고 그렇지 않으면 A에서 고른 원소를 뺀 후에 다시 각 집합에서 원소를 골라 확인하는 과정을 A가 공집합이 될 때까지 반복합니다. 

    그러면 마지막에 고른 B의 원소가 독침이 되고 이를 통해 꼬리와 몸통을 찾아 전갈 그래프인지 확인할 수 있습니다.

     

    이 방법으로는 처음 꼭짓점의 연결 관계를 파악할 때 n-1 번, 독침, 꼬리, 몸통을 찾을 때 각각 n-2 번, n-2 번, n-3 번, 몸통이 독침을 제외한 모든 꼭짓점과 연결되어 있는지 확인할 때 n-4 번으로 질문이 최대 5n-12 번 소요되네요. (정확히는 B에서 꼬리를 고르지 않는 경우를 따져서 최대 5n-13 번)

    이것보다 질문 횟수를 더 줄이는 방법이 있을까요?

    댓글 작성하기 좋아요0 댓글수3
    •  
      B.C.I.수학장 Lv.5 2021.04.11 22:10

      https://koosaga.com/130 여기 나온 방법이랑 정확히 일치하는데... 혼자 생각해낸 게 맞으신지요?

      좋아요0
    •  
      바람개비 Lv.3 2021.04.12 00:20

      네, 문제 보고 떠오른 방법 그대로 적은겁니다.

      좋아요0
    •  
      통계의끝을본남자 Lv.8 2021.04.12 15:54

      이 방법이 맞다고 가정하면 n이 자연수인 경우에는(질문 개수는 당연히 자연수이겠죠?) 5n-13이 300n보다 클 수 없으니까 당연히 답은 가능하다 아닌가요?

      좋아요0
  •  
    B.C.I.수학장 Lv.5 2021.04.11 22:13

    Green55님, wookje님 팬이에요 :blobaww:

    댓글 작성하기 좋아요0 댓글수1
    •  
      사인 Lv.3 2021.04.12 07:54 비밀댓글
      비밀 댓글이 등록 되었습니다!
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911