어떻게 친구의 가능한 모든 그룹을 찾으려면 <a href="https://i.stack.imgur.com/NZFdX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NZFdX.png" alt="Friendship graph"></a></p> <p>을 다음과 같이

-3

나는 우정 그래프가 친구 그룹의 총 수를 찾습니다. 이러한 그룹화를 찾는 가장 좋은 알고리즘은 무엇입니까? 예를 들어이 그래프에서 가능한 우호 그룹은 다음과 같습니다. 1,2,3,4,12,13,23,123,14,143,124,1234어떻게 친구의 가능한 모든 그룹을 찾으려면 <a href="https://i.stack.imgur.com/NZFdX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NZFdX.png" alt="Friendship graph"></a></p> <p>을 다음과 같이

브 루트 포스 알고리즘을 사용하면 (각 정점에서 시작하여 4 시간), 그것은 많은 중복을 생성합니다.

그래프 데이터 형식을 제공 할 수 있습니까? –

가장 흥미로운 질문은 가장 적은 수의 오류를 발생시키는 선형 알고리즘을 찾는 방법 (그리고 오류 계수 함수 정의) –

@igael 그래프는 대부분이 부족할 수 있기 때문에 인접 목록으로 저장하는 것이 좋습니다. 사례. –

Wikipedia에 따르면 NP 완료이므로 이러한 세트를 감지하기 위해 무차별 대항력 만 사용할 수 있습니다. 이 문제는 Clique problem라고하며 처음으로 확인 된 NP 완전 문제 중 하나입니다.

2016-09-28 12:06:22 xenteros

예 NPH입니다. 스파 스 그래프에 대한 더 빠른 알고리즘을 찾고 있습니다. –

http://arxiv.org/abs/1209.5818 – xenteros

감사합니다. –

답변