최소한의 스패닝 트리 문제를 해결하는 데 붙어 있습니다

Question

그래프에서 최소한의 스패닝 트리를 찾는 데 문제가 줄었습니다. 하지만 나는 하나 더 제약을 원합니다. 각 정점의 총 정도는 특정 상수 요인을 초과해서는 안됩니다.. 내 문제를 어떻게 모델링합니까? MST가 잘못된 길입니까? 저를 도와 줄 알고리즘을 알고 있습니까?

한 가지 더 문제 : 내 그래프는 중복 에지 가중치가있어 고유 한 MST의 수를 계산할 수있는 방법이 있습니까? 이것을하는 알고리즘이 있습니까?

감사합니다.

편집 : 학위별로, 나는 정점을 연결하는 총 가장자리 수를 의미합니다. 중량 중량은 두 개의 가장자리가 같은 무게를 가지고 있음을 의미합니다.

Answer 1

이 논문 어느 최대 정도의 스패닝 트리 D : http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// 원래 링크 편집은 현재 비활성 상태입니다. http://research.microsoft.com/pubs/80193/mbdst.pdf 대신에.

Answer 2

글쎄, 해결책이 없다는 것을 증명하기는 쉽습니다. 입력 그래프를 한계보다 높은 수면이있는 트리를 입력 그래프로 만드십시오.

Answer 3

Garey Johnson은이 문제가 해밀턴으로 줄어들 었습니다. http://caislab.icu.ac.kr/lecture/data/2003/spring/ice514/project/m03.ppt그러나 더 나은 작업 모델에 감사합니다 ...

계산 : http://mathworld.wolfram.com/spanningtree.html . 이에 따르면 Mathematica에는 기능이 있습니다. 이것에 대한 제안이 있습니까?