그래프에서 클린크를 찾는 방법은 무엇입니까?

Ruby와 Ruby 그래프 라이브러리를 사용하고 있습니다. http://rgl.rubyforge.org/그래프에서 클린크를 찾는 방법은 무엇입니까?

그래프에서 전체 클레임 (전체 하위 그래프)을 찾는 방법은 무엇입니까?

특히 두 개의 특정 꼭지점이 관련된 5 개의 도발을 찾고 있습니다.

는 I가 정말로있어 무엇 - 프로젝트 오일러 Problem 60

소수 3, 7, 109, 및 673, 매우 놀라운 있습니다. 임의의 두 소수를 취하여 임의의 순서로 연결하면 결과는 항상 소수가됩니다. 예를 들어, 7과 109를 취하면 7109와 1097이 모두 소수입니다. 이 4 개의 소수의 합인 792는이 속성을 가진 4 개의 소수의 집합에 대해 가장 낮은 합을 나타냅니다.

두 소수가 연결되어 다른 소수를 생성하는 다섯 소수의 집합에 대한 최저 합을 찾습니다.

십진수 'pq'와 'qp'가 모두 소수 일 경우 내 그래프의 꼭지점은 p에서 q 사이입니다.

출처

2012-11-10 Colonel Panic

은 당신이 가장 큰 파벌을 찾기 위해 NP 완전 문제의 실현합니까? –

알고리즘에 따라, 'O (v^5)'에서 5 클릭을 찾는 것은 꼭지점을 반복하고 가장자리가 있는지 확인할 수있는 한 매우 간단합니다. –

알고리즘에 따라 두 개의 정점이 주어지면 나머지 세 개를 찾는 것은'O (v^3)'에서 간단합니다. –

특히 저는 두 개의 특정 꼭지점이 포함 된 5 개의 도발을 찾고 있습니다.

가정 두 정점은 first하고 second

common = ug.adjacent_vertices(first) & ug.adjacent_vertices(second) 

for triple in common.combination(3) 
    a,b,c = triple 
    if ug.has_edge?(a,b) && ug.has_edge?(a,c) && ug.has_edge?(b,c) 
     return [first,second,a,b,c]

출처

2012-11-10 23:13:55

그래프에서 클린크를 찾는 방법은 무엇입니까?

답변

관련 문제