신장 부분 그래프: 두 판 사이의 차이

 

[[연결|연결 그래프]]된 [[무방향 그래프]]에서 [[신장트리]]는 모든 [[정점]]을 최소한의 간선 수로 연결하는 [[트리]]를 뜻한다. 따라서 하나의 그래프에는 수많은 신장트리가 있을 수 있다. 이 때 이 그래프의 [[간선]]에 가중치가 있다고 하면, 같은 그래프의 신장트리간에도 서로 가중치의 합이 달라질 수 있는데 최소비용 신장나무는 이 가중치의 합을 최소로 한 신장트리를 뜻한다.