무향 그래프 <strong>모든</strong> K-클리크를 카운트 순차적

Question

합니까은 순차 알고리즘이 존재 그래프에서 k 개의 꼭지점 모두 클리크 계산?

k- 클릭이란 말은 무 디렉션 그래프에서 모서리로 서로 연결된 버텍스 세트 수입니다.

다음은 도발에 대한 자세한 설명입니다. https://en.wikipedia.org/wiki/Clique_(graph_theory)

Answer 1

Bron–Kerbosch algorithm을 사용하면 그래프의 모든 클록을 나열 할 수 있습니다. 그래프의 모든 클리크를 반복하면서 각 재귀 호출

BronKerbosch1(R, P, X): 
    if P and X are both empty: 
     report R as a maximal clique 
    for each vertex v in P: 
     BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) 
     P := P \ {v} 
     X := X ⋃ {v} 

, R는 도당을 포함하는 집합 : 그 구현 siplest (위키 의사)을 고려한다. 그러므로 크기가 k 일 때마다 클릭을 인쇄하도록 알고리즘을 변경하고 재귀 호출은 더 큰 클록을 생성하기 때문에 재귀를 잘라낼 수 있습니다.

BronKerbosch1(R, P, X, k): 
    if |R| = k: 
     report R as a k-clique 
    else 
     for each vertex v in P: 
      BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) 
      P := P \ {v} 
      X := X ⋃ {v} 

피벗 및 정점 순서가있는 최적화 된 버전을 구현할 때 같은 생각을 사용할 수 있습니다.