선택된 버텍스의 최소 스패닝 트리를 찾는 알고리즘

Question

버텍스/노드 및 에지/링크 집합의 최소 스패닝 트리/그래프를 찾기 위해 프랭크의 알고리즘이나 크루스 칼의 알고리즘을 사용할 수 있습니다. 그래도 내가 원하는 것은이 컬렉션의 최소 스패닝 그래프를 찾는 알고리즘이지만 결과 그래프는 모든 노드 대신 임의로 선택한 노드 만 포함시켜야합니다. 결과 그래프에 필요한 노드보다 더 많은 노드가 포함되어 있으면 괜찮습니다.

이러한 알고리즘이 있습니까? 아마도 필요한 노드 만 포함하도록 그래프를 수정 한 후 Prim (또는 Kruskal) 알고리즘을 사용할 수 있습니까? 그러나 그래프의 연결성을 유지하면서 그래프를 수정하는 방법을 모르겠습니다. 우리가 임의 단지는 노드와 D가 필요하다고 결정, 이제

A 
(2)/ \(1) 
    B C 
(2)\ /(5) 
    D 

: 예를 들어

, 우리는 (괄호 링크의 비용) 시작 그래프 모양의 다이아몬드를 말한다. 우리가 A에서 시작했다면 ((2 + 2) < (1 + 5)), 왼쪽 경로를 취하기를 원할 것입니다.

A 
(2)/ \(1) (2) 
    B C ------E 
(2)\ /(5) 
    D 

우리가 A, D 노드 및 E 필요한 경우에만 것을 결정하는 경우에, 우리는 최소한의 비용으로 경로가 반드시 가장 적은와 하나가 아닌 것을 깨닫게 :

우리가 약간 그래프를 수정하는 말 모래밭. A - B - D 및 A - C - E 비용은 7이지만 A - C - D 및 C - E 비용은 8입니다.

Answer 1

원하는 것은 이산 Steiner tree입니다. 그래프의 모든 정점이 필수는 아니지만 선택 사항 정점에서 트리가 분할 될 수있는 경우 문제는 NP 하드입니다.

위키 피 디아 (Wikipedia)는이 문제에 대해 다음과 같이 말합니다. 일반적으로 임의의 좋은 근사 비율은 일반적으로 다항식 시간에서 얻을 수 없다고 생각됩니다. 최소 Steiner 트리의 근사치 1.39를 찾는 다항식 시간 알고리즘이 있습니다.