Prufer code에 대하여
Graph Theory

Prufer code에 대하여

728x90
반응형

u는 독일어 움라우트 표기해야한다.

prufer code는 트리구조를 인코딩하는 방법으로 n개 정점을 가진 트리를 n-2개 정수로 표현한다.

트리로부터 프뤼퍼코드를 생성하거나 프뤼버코드로부터 트리를 생성하는 예제는 2024 그래프이론 퀴즈와 중간고사 모두에서 출제되었으므로 후배님들은 확인해보길바란다.

 

그냥 공부했던 내용을 기록하기 위해 붙여둔다.

Generate Prufer code

 

generate tree from prufer code

 

728x90
반응형
저작자표시

'Graph Theory' 카테고리의 다른 글

Assign integer weights to the edges of Kn. Prove that the total weight on every cycle iseven iff the total weight on every triangle is even.  (0) 2024.12.28
Determine which trees have Pr¨ufer codes that (a) contain only one value, (b) containexactly two values, or (c) have distinct values in all positions.  (0) 2024.12.28
Show konig thm implies Hall’s thm  (0) 2024.12.28
For all positive integers r and d that satisfy r ≤ d ≤ 2r, construct a simple graphwith radius r and diameter d.  (0) 2024.12.28
Use part (a) to prove that diam(G) ≤ 2rad(G) for every graph G.  (0) 2024.12.28

    티스토리툴바