Campus Coder

신장 트리(spanning tree) G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리 신장트리는 G의 최소 부분 그래프(간선의 수가 가장 적은 부분 그래프) G'로서 V(G') = V(G)이고 G'는 연결되어 있음 신장트리는 n-1개의 간선 가짐 최소 비용 신장 트리 최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 사용 신장 트리의 제한 조건 그래프 내에 있는 간선들만을 사용 정확하게 n-1개의 간선만을 사용 사이클을 생성하는 간선을 사용 금지 Kruskal 알고리즘 한 번에 하니씩 T에 간선을 추가해 가면서 최소비용 신장트리 T를 구축 T에 포함될 간선을 비용의 크기 순으로 선택 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가 G는 연결되..

그래프 정의 그래프 G: 2개의 집합 V, E로 구성 V: 공집합이 아닌 정점(vertex)의 유한집합 E: 간선(edges)이라고 하는 정점 쌍들의 집합 표기: G = (V, E) 그래프의 제약 사항 자기 간선 또는 자기 루프 없음 동일 간선의 중복 없음 무방향 그래프 간선을 나타내는 정점의 쌍에 순서 없음 (u, v) = (v, u) 방향 그래프 방향을 가지는 정점의 쌍 로 표시 ≠ 완전 그래프 n개의 정점과 n(n-1)/2개의 간선을 가진 그래프 그래프 G의 부분그래프(subgraph) v(G') ⊆ V(G) 이고 E(G') ⊆ E(G)인 그래프 G' (u, v)가 E(G)의 한 간선이라면 u와 v는 인접 간선 (u, v)는 정점 u와 v에 부속 정점 u로부터 정점 v까지의 경로 그래프 G에서 \(..