1건의 항목
그래프 용어 V : vertex E : Edge path 연결 그래프 : 어떤 두 정점 사이에도 경로가 존재하는 그래프 부분 그래프 가중치 포함 그래프 : Edge에 가중치가 달려있음 순환 경로 순환 그래프, 비순환 그래프 트리 - 비순환, 비방향그래프 신장 트리 : 연결된, 비방향성 그래프에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 하는 트리 신장 트리의 개수는 Cayley’s formula에 따른 개수를 가짐 최소비용신장트리 신장 트리가 되는 부분 그래프 중에서 가중치가 최소가되는 부분 그래프 무조건 트리로 나온다.