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

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

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

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

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

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

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

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

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

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

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