平面图问题,初步组合分析问题

题目

平面图问题,初步组合分析问题
1.具有6个顶点,12条边的连通简单平面图中,次数为3的面有几个?
2.1400的不同正因子个数是?

答案

1.V=6,E=12,连通简单平面图,欧拉示性数 F-E+V=2 ==》 F=8
设 F=a3+a4+...+an,其中 ai 为 次数为i的面的个数.于是
a3+a4+...+an=8
2E=3a3 + 4a4+..+nan
即：
24=3a3 + 4a4+..+nan
8=a3+4/3 a4+...+ n/3 an
0= 8-(a3+a4+...+an) =1/3 a4+...+ n/3 an
因为 ai>=0,i=3,...,n.所以必须有 a4=...=an=0,于是 a3=8
即次数为3的面有8个
2.1400= 2^3*5^2*7
所以 1400的正因子个数为：(3+1)*(2+1)*(1+1)=24.