一直没啥想写的,不过最近又看见一道和欧拉示性数公式相关的思维题,所以萌生出了写这篇博客的想法。
首先是关于平面图欧拉示性数公式的定义:
设$G$是一个连通的平面图,顶点的数目为$V$,边的数目为$E$,面的数目为$F$,则有$$V+F-E=2$$
下面使用数学归纳法进行证明:
- 当$E=0$时,有$V=1,F=1$,等式显然成立。
- 假设当$E=k$时等式成立,下面考虑$E=k+1$的情形。
- 当图中无环时易知$V=k+2,F=1$,等式显然成立。
- 反之,我们设$e$为环中的一条边,那么对于图$G\setminus\set{e}$由假定知等式成立(即为$E=k$的情形,令其$V=v_0,F=f_0$,则$v_0+k-f_0=2$)。那么对于图$G$我们有$V=v_0,E=k+1,F=f_0+1$,因此等式也成立。
综上,由数学归纳法可知等式对于$E\geq0$的情形皆成立。
具体使用
声明
下面这种方法只在本人太闲了弄出来玩的,实际体验并不一定好。
简单来说就是固定了边数,在使点数尽可能小,从而使之面的数目最大化。
题目描述
平面上有n个圆,求使这n个圆两两相交(即每两个圆之间恰好有两个交点)后最多能把平面划分成多少个区域。
对于圆这样的图形,我们不方便计算它的各项参数,可以直接将其边无限细分,即假定点数为$m$,则边也为$m$。由于$m$无穷大,两圆相交时并不会产生新的边,但是会减去重叠的两个点。
所以,当一共有$n$个圆时,图上的各项参数为 $$E=n\times m,V=n\times m-2\times {n \choose 2},F=2+E-V=2+n\times(n-1)$$
|
|
我觉得不需要题目描述了,标题即描述。
由于折线比较特殊,不方便定义端点,我们可以先直接划定边界,例如放一个圆$V=n_0,E=n_0$,但此时圆外的区域不能算作一块平面。同时,折线就可以改成两条共端点的线段。
然后就按常规的来,无穷细分一条线段为$V=k,E=k-1$。则当共有$n$条折线时,图的各项参数(使$F$最大的情况,由于边数确定即交点尽可能多)为
$$E=n_0+n\times2(k-1),V=n_0+n\times(2k-1)-2n-4\times{n \choose 2}$$
所以$F=1+E-V=1+n+2n(n-1)$
|
|