차수열 (2) 썸네일형 리스트형 하벨-하키미 알고리즘 (Havel-Hakimi Algorithm) 티스토리 블로그 관리 페이지에는 유입 키워드를 확인할 수 있는 기능이 있습니다. 저는 하루에 몇 번씩 유입 키워드를 살펴보면서 어떤 검색어로 제 블로그에 유입되는지를 확인하고는 합니다. 그러다 최근 'hakimi 방식', 'hakimi의 방법' 등의 키워드로 제 블로그에 방문한 사람이 있다는 사실을 알게 되었습니다. 최근에 제가 작성한 거리의 그래프 실현 가능성에 대한 포스트로 유입된 것이었습니다. 2022.05.15 - [수학적 도구/Graph theory] - 거리의 트리 실현 가능성 (Tree Realizability of Distance) 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로.. 그래프 트리에 관한 간단한 성질들 요즘 트리(tree, connected acyclic graph)에 관한 문제를 고민하고 있는데, 오늘 그에 관한 간단하지만 흥미로운 성질들을 알게 되어 정리합니다. 너무 간단해서 학부 수준의 조합론에서 분명 다루었을 내용으로 보입니다만, 저는 전공이 컴퓨터과학이니까요. 채워야할 것들이 아직도 너무 많은 것 같습니다. 차수열(degree sequence)에 관한 필요충분조건 첫 번째는 tree의 degree sequence에 관한 내용입니다. 먼저 degree sequence가 무엇이냐면, 그냥 정점의 차수를 내림차순으로 나열한 것입니다. Degree sequence는 그래프의 모양을 가늠할 수 있는 좋은 도구입니다. 다만, 하나의 degree sequence가 유일한 그래프를 결정하는 것은 아닌데요. .. 이전 1 다음
