수학적 도구/Graph theory (3) 썸네일형 리스트형 하벨-하키미 알고리즘 (Havel-Hakimi Algorithm) 티스토리 블로그 관리 페이지에는 유입 키워드를 확인할 수 있는 기능이 있습니다. 저는 하루에 몇 번씩 유입 키워드를 살펴보면서 어떤 검색어로 제 블로그에 유입되는지를 확인하고는 합니다. 그러다 최근 'hakimi 방식', 'hakimi의 방법' 등의 키워드로 제 블로그에 방문한 사람이 있다는 사실을 알게 되었습니다. 최근에 제가 작성한 거리의 그래프 실현 가능성에 대한 포스트로 유입된 것이었습니다. 2022.05.15 - [수학적 도구/Graph theory] - 거리의 트리 실현 가능성 (Tree Realizability of Distance) 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로.. 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로 포스팅을 할 생각도 있었는지라 블로그에 글을 쓰는 것이 늦어졌습니다. 색다른 주제는 바로 양자 컴퓨팅(quantum computing)입니다. 하도 화제인지라 개인적으로도 공부해 보고 싶었습니다. 처음에는 전혀 이해가 되지 않았는데 이 책 저 책 찾아보면서 공부하다 보니 이제는 좀 이해가 되는군요. 언젠가 해당 주제로 포스팅을 해 보도록 하겠습니다. 각설하고, 이번 글의 주제를 고민하게된 배경에 대해서 간략히 설명을 드리겠습니다. 요새 온라인 메트릭 매칭 문제(online metric matching problem)를 (제가 찾아본 바로는) 기존에는 없던 새로운 모델에서 해결해 보는 연구를 진행하고 있습니다. 그런데 일반적인 메.. 그래프 트리에 관한 간단한 성질들 요즘 트리(tree, connected acyclic graph)에 관한 문제를 고민하고 있는데, 오늘 그에 관한 간단하지만 흥미로운 성질들을 알게 되어 정리합니다. 너무 간단해서 학부 수준의 조합론에서 분명 다루었을 내용으로 보입니다만, 저는 전공이 컴퓨터과학이니까요. 채워야할 것들이 아직도 너무 많은 것 같습니다. 차수열(degree sequence)에 관한 필요충분조건 첫 번째는 tree의 degree sequence에 관한 내용입니다. 먼저 degree sequence가 무엇이냐면, 그냥 정점의 차수를 내림차순으로 나열한 것입니다. Degree sequence는 그래프의 모양을 가늠할 수 있는 좋은 도구입니다. 다만, 하나의 degree sequence가 유일한 그래프를 결정하는 것은 아닌데요. .. 이전 1 다음
