빈 그래프는 수형도인가

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

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

주차 문제와 케일리의 공식, 그리고 조합적 증명

다음과 같은 상황을 생각한다. 대의 자동차들이 있고, 개의 주차 스팟 이 일렬로 주어져있다. 각각의 자동차마다 선호하는 주차스팟이 하나씩 있으며, 번째 자동차의 선호 스팟을 라 한다. 이 자동차들이 일렬로 들어가며 각각 차례로 원하는 스팟에 주차하되, 만약 그곳에 다른 차가 이미 있었다면 다음 스팟에 주차를 시도한다고 한다. (만약 다음 스팟에도 차가 있으면 그 다음 스팟을 보는 식) […]

Read More 주차 문제와 케일리의 공식, 그리고 조합적 증명