빈 그래프는 수형도인가

트위터에서 empty graph가 tree가 아닌 forest로 분류되어야하는지에 대한 이야기가 있었는데 (원본 트윗은 쓰신 분이 플텍 걸어놔서 보이지 않는다) 여러모로 봤을 때 forest로 보는 것이 타당하다. 이게 문제가 된 이유는 tree의 정의들을 생각해보면 ‘임의의 두 점이 정확히 한 개의 경로로 연결되는 그래프’, ‘연결되고 cycle이 없는 그래프’ 등이 있는데 전자 같은 경우 뽑을 두 점이 애초에 없으니 […]

Read More 빈 그래프는 수형도인가

랜덤 워드에서 특정 워드가 등장할 확률 (3)

이전 글: (1), (2) 이전 글에서는 알파벳 집합이 , 그 사이즈가 로 정해져있을 때 특정 워드 가 들어가지 않는 길이 의 워드 개수는 의 해들로 표현될 수 있음을 보였다. (은 의 길이, 는 의 순환주기) 이 특성방정식을 에 대해 미분한 식과 이 식이 공통근을 갖지 않으므로 중근이 없어, 더 정확히 말하자면 이 해들의 거듭제곱의 선형합이라 […]

Read More 랜덤 워드에서 특정 워드가 등장할 확률 (3)