수업시간에 generating function of the number of spanning forest of the graph를 배웠습니다. 이때 vertex의 수를 n, component의 수를 k로 놓고 k가 1부터 n일 때까지(1일 때는 spanning tree의 개수가 되고, n일 때는 모든 vertex가 혼자 있어야 되므로 항상 1) 계수가 존재한다고 배웠는데요,
교수님께서는 이때 Planar graph의 Euler characteristic을 위 계수들의 alternating sum으로 정의하셨습니다만, 이때의 characteristic이 통상적으로 알려진 betti number로 정의된 characteristic과 값이 같은지가 궁금합니다.
도와주세요, 부탁드립니다.
다르겠죠. 그래프 G에 대해서 τ(G)를 말씀하신 alternating sum으로 정의한다면, 정점 집합이 disjoint한 두 그래프 G1과 G2에 대해서 τ(G1 ∪ G2) = τ(G1)τ(G2)를 만족할수밖에 없는데, G1, G2가 planar하면 G1∪G2도 마찬가지로 planar하니 이 패러미터가 planarity 하에서 불변이라고 말할수가 없고요, 그리고 작은 예시를 통해서 확인해보면 간선 딸랑 하나있는 그래프 K_2에 대해서 τ(K_2)를 계산하면 component 하나짜리 forest는 자신 1개, component 두개짜리 forest도 마찬가지로 한개라서 τ(K_2) = 1 - 1 = 0을 얻습니다.