[알고리즘] Kruskal 알고리즘 - 최적 여부의 검증 - 크루스칼

소개글

[과제7] Kruskal 알고리즘 - 최적 여부의 검증 -입니다.

목차

1. 보조정리
2. 증명

본문내용

크루스칼 알고리즘이 항성 최적의 해답을 준다고 증명하기 위해서 다음의 보조정리가 필요하다.

⦁ 보조정리
G(V,E)는 연결된 가중치 포함 비방향 그래프, F는 E의 유망한 부분집합, e는 F∪{e}하여 순환이 생기지 않도록 해서 E-F에 속한 최소 가중치 이음선이라 하자. 그러면 F∪{e}는 유망하다.
증명 : F가 유망하기 때문에 다음 식을 만족하는 이음선의 집합 F'이 존재해야 하고
F⊆F' (V,F')는 최소비용 신장 트리이어야 한다.

참고 자료

없음