나무 그래프: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
→성질: 오타 수정 |
잔글 봇: 문단 이름 변경 (바깥 고리 → 외부 링크) |
||
78번째 줄:
모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다.
# 우선, 각 꼭짓점 <math>v</math>에 대하여 양의 정수 값의 변수 <math>\mathtt{d}_v</math>를, <math>v_i</math>가 프뤼퍼 열에 등장하는 수 + 1로 놓는다.
# 프뤼퍼 열의 첫째 꼭짓점 <math>y_0</math>에 대하여, <math>\mathsf d_v=1</math>인 최소의 꼭짓점을 <math>v</math>라고 하면,
## 변 <math>(v,a_v)</math>를 [[그래프]]에 추가하며,
## <math>\mathtt d_{y_0}</math>과 <math>\mathtt d_v</math>를 각각 1만큼 감소시킨다.
# 위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다.
173번째 줄:
{{각주}}
==
* {{eom|title=Tree}}
* {{매스월드|id=Tree|title=Tree}}
| |||