정점의 개수가 n인 연결그래프로부터 생성 가능한 신장트리(spammin… | [계리직 컴퓨터일반] 16년 1회차 기출문제 상세 페이지

정점이 n 개인 연결그래프의 신장트리는 항상 n-1 개의 간선을 가진다.
신장트리는 모든 정점을 사이클 없이 연결한 트리이며, 정점 n 개를 하나로 잇는 트리의 간선 수는 정확히 n-1 이다.
간선이 n 개면 반드시 사이클이 생겨 트리가 아니다.
$\dfrac{n(n-1)}{2}$ 는 무방향 완전그래프의 간선 수이다.
$n^{2}$ 은 인접 행렬의 원소 수로, 신장트리의 간선 수와 무관하다.