특정 노드의 차수를 최소화하는 최소 스패닝 트리

Question

(모든 최소 스패닝 트리 중에서) 노드의 차수를 최소화하는 최소 스패닝 트리를 어떻게 찾을 수 있습니까?

동일한 무게의 여러 가장자리가있는 경우 v을 만지지 않는 것을 선택하면 Kruskal 알고리즘이 문제를 해결할 수 있습니까?

Answer 1

질문에 부분적으로 대답하려면 질문에서 스케치 된 Kruskal 알고리즘을 수정해도 문제가 해결되지 않습니다.

V = {1,2,3}, 
E = {{1,2}, {2,3}, {3,1}}, 
w({1,2}) = 1, 
w({1,3}) = 1, 
w({2,3}) = 2 

및 1이 최소 스패닝 트리의 정도가 최소화되어야하는의 노드 그래프 G=(V,E,w)을 고려하십시오. 그런 다음, 가장자리는

S1={{1,2},{1,3}} 

무게 2의 최소 스패닝 트리를 구성 설정합니다. 그러나 Kruskal 알고리즘의 수정 된 버전은 일반성의 손실없이 {1,2}을 선택하면 {1,3}이 금지되어 결과적으로 {2,3}이 선택됩니다. 전체에서, 선택된 에지의

S2={{1,2},{2,3}} 

노드 1가 S2보다 낮은 정도를 가지고있다, 그러나 S2의 총 중량은 최소 스패닝 트리를 포함하지 않는 것을 의미한다 3이다.

또한 최소화 될 노드 v의 정도는 적어도 3 최소 스패닝 트리에 v 이상의 이웃의 가능성을 가지고 있어야한다 있습니다.

전체 검색에서 v의 가능한 인접점을 선택하십시오. v에는 최대 n 개의 이웃이 있으므로 이웃은 많아야 2^n입니다. Prim에 의한 알고리즘을 사용하여 이들 각각을 선택된 이웃 v을 포함하는 비용면에서 최소 인 스패닝 트리로 확장합니다. 최소 비용 인 이러한 모든 솔루션에서 v의 차수가 최소화 된 솔루션을 선택하십시오. 그러나이 방법은 다항식 시간 알고리즘을 생성하지 않습니다.