ullmann 알고리즘을 설명 할 간단한 예제가 있습니까

Question

Im는 그래프 이론을 배우는 중 신입생입니다. 지금은 (하위) 그래프 동형을 배우고 있습니다. 두 가지 중요한 알고리즘이 있습니다 : 울름의 알고리즘과 vf2.

저는 Ullmann의 논문을 읽었습니다 : 서브 그래프 동형의 알고리즘. 나는 또한 그것을 봤 거든 구글 나를 많이 응용 프로그램을 준,하지만 알고리즘의 절차를 이해할 수 없습니다.

간단한 설명을 제공해 주시겠습니까?

Answer 1

This answer 관련 질문에 대해서는 Ullmann 알고리즘의 소스 코드를 제공합니다.

These slides 예제를 제공하지만 알고리즘의 주요 구성 요소는 슬라이드 "Ullmann 's Algorithm V2"의 예제가없는 경우에만 언급됩니다.

그래서 아래 예제를 제공합니다. GB가 GA와 같은 하위 그래프를 가지고 있는지 여부를 알고 싶습니다. 즉, GA의 정점을 GB의 정점에 매핑하여 GA의 모서리가 GB의 모서리에 매핑되도록하려고합니다. 원래 종이와 슬라이드 모두가 M이라는 행렬을 사용하지만, 코드가하지 않는 것을

는

참고. 왜냐하면 행렬은 코드에서 possible_assignments [i]가 나타내는 것과 동일하기 때문입니다. i 번째 정점이 j 번째 정점 인 GB에 매핑 될 수있는 경우 M [i] [j]는 1입니다. GB의 정점 u를 매핑 할 수있는 GB 정점 집합에 대해 후보 (u) 등을 사용할 것입니다.

첫 번째 관찰은 GA의 꼭지점을 적어도 큰 정도의 GB 꼭지점에만 매핑 할 수 있다는 것입니다. 초기에 후보 (u) = 후보 (v) = {a, b, e, f, g}, 후보 (w) = {f} 및 z의 후보는 모두 GB의 정점입니다.

이제 Ullmann의 알고리즘의 주요 구성 요소 인 "M 수정"절차를 처음 수행합니다. 즉, GB의 정점 x가 GA의 정점 y에 대한 후보 중 하나 일 때마다 y의 모든 이웃은 x의 이웃 중에서 적어도 하나의 후보를가집니다. 이 검사가 실패하면 y의 후보에서 x를 제거합니다. 더 이상의 삭제가 불가능해질 때까지 이러한 삭제를 확인합니다.

예를 들어, h는 z의 후보 중 하나입니다. 그러나 w는 z의 이웃이지만 h의 이웃 (즉, g)은 모두 cadidate (w) = {f}에 속하지 않습니다. 따라서 에지 {w, z}가 비 에지에 매핑되므로 z를 h로 매핑 할 수 없습니다. 따라서 우리는 h를 후보자 (z)로부터 안전하게 제거 할 수 있습니다. 정교화의 결과는 후보자 (u) = 후보자 (v) = 후보자 (z) = {a, e, g} 및 후보자 (w) = {f}입니다.

이제 우리는 백 트랙킹을 시작합니다.

먼저 u를 a로 매핑 해보십시오. 즉, 후보 (u) = {a}를 설정하고 다른 후보 세트에서 a를 제거합니다. Refine은 e 나 g가 a의 이웃이 아니므로 후보 e와 g를 제거합니다 (v). 후보자 (v)가 비어있어이 지점에서 다시 돌아옵니다. 후보자에 대한 변경을 취소합니다.

이제 u를 e로 매핑 해 보겠습니다. 다시 말하지만 후보자 (v)는 결국 비어있게됩니다.

마지막으로 동일한 결과로 u를 g로 매핑 해 봅니다.

우리는 GA가 GB의 하위 그래프가 아니라고 결론 내립니다. 모든 8 * 7 * 6 * 5 과제를 시도하지 않고도.

Ullmann이 초기에 GA의 정점을 내림차순으로 정렬한다는 사실을 잊어 버렸습니다. 그러나 큰 차이를 만들지는 않을 것입니다. 우리는 w가 f에 대해서만 매핑 될 수 있다는 것을 먼저 알아낼 것입니다. 그런 다음 우리가 얻은 결과와 정확히 동일한 결과로 u에 대한 분기를 계속할 것입니다.