2024年1月7日发(作者：初2数学试卷图片人教版)

习 题 十 一

1．设p11，证明任何p阶图G与G总有一个是不可平面图。

分析：

G与G是两个互补的图，根据互补的定义，互补的图有相同的顶点数，且G的边数与G的边数之和等于完全图的边数p(p-1)/2；而由推论11.2.2，有任何简单平面图G，其顶点数p和边数q满足：q≤3p-6。

证明. 若G(p,q)与G(p,q)均是可平面图，则

q3p6 （1）

q3p6 （2）

但pp,qp(p1)q （3）

121p(p1)q3p6

22整理后得

p7p122q 又由（1）有

将（3）代入（2）有

p7p122(3p6)

即

p13p240

221313242413132424p也即 .

2213731373得

p22 得2p11

此与p11矛盾。

因此任何p阶图G与G不可能两个都是可平面图，从而G与G总有一个是不可平面图。

2．证明或否定：两个p阶极大简单平面图必同构

分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；两个p阶极大简单平面图不一定同构。

解：令p6，三个6阶极大简单平面图G1,G2,G3如下：

454534344534444354G1G2G3

顶点上标的数字表示该顶点的度，但显然不同构.

3．找出一个8阶简单平面G，使得G也是平面图.

分析：由第1题证明过程可知，当p<11时，G和G可以同时为平面图。

解：如下平面图G，显然其补图也是平面图。

67347GG

4．证明或者否定：每个极大平面图是H图.

分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；而H图是存在一个H回路的图，即存在一条经过图中每一个顶点一次且仅一次的回路。由定理11.1.2知极大平面图的每个面都是三角形，因此G中必存在回路，利用最长回路的性质使用反证法可证明每个极大平面图都是H图。

证明：设G是极大平面而不是H图.显然G必连通且有回路.

设c是G中最长的回路cuv1v2vnu，由假设，

存在wv(G)不在c上且w与c上vi和vi1构

成一个三方形，于是

v1cviwvi1vnuv1v2vi

uv1viwvi1vnu

从而|c||c|.矛盾，故G是H图。

uwviv2vi1

5．试证明：若平面图G的每个面都是三角形k3，则G是极大平面图。

分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；利用这个定义使用反证法可证明本题。

证明：设平面图G的每个面都是k3，若G不是极大平面图.则G中存在u,vV(G)，使得vnuvE(G)，且Guv仍为平面图

设uv是Guv中两个面fi和fj的公共边界.于是，G中fi与fj的面是一个面fk ，显然d(fk)3，由此与G的每个面都是k3矛盾.

6．设G(p,q,r)是有k个分支的平面图，试证明：

pqrk1

分析：由欧拉公式任何简单连通平面图G(p,q,r)均满足pqr2,对G的k个连通利用归纳法使用该结论可证明本题。

证明：当k1时，即欧拉公式，下设k2，G有k个分支.

G1(p1,q1,r1),,Gk(pk,qk,rk).由欧拉公式有pi-qi+ri=2;

但

pi1kip,qiq，rirk1

i1i1kk故

pqrk12k

即

pqrk1

7．证明：k5e是平面图，其中e∈E（K5）

分析：由于k5 的对称性,只须考虑其中的一条边e，验证k5e是可平面图即可.

证明：任选k5的某条边e，则k5e如下图所示，显然这是一个平面图。

8．证明：k3,3e是平面图，其中e∈E（K3，3）

分析：仿照第7题，由于k3,3的对称性，因此也只须考虑其中的一条边e，验证k3,3e是可平面图即可.

证明：任选k3,3的某条边e，则k3,3e如下图所示，显然是一个平面图。

9．一个图的围长是图中最短回路之长度，若图中无回路，则围长定义为无穷大。证明：如果G(p,q,r)是连通平面图，围长g≥3且有限，则

q≤g(p-2)/(g-2)

)分析：由定理11.1.1 对任何平面图G(p,q,r)，满足

d

(

f

i

2

q ，又由于G是简单连通图，i1r因此还满足欧拉公式pqr2。利用这两个结论可证明本题。

证明:由于G的围长为g,故d(fi)≥g，由定理11.1.1知：

r

grd(fi)2q

i1可以得到

r2q/g将它代入Euler公式就可以得到q≤g(p-2)/(g-2)

10．利用题9证明Peterson图是不可平面图。

分析：Petersen图参看书上80页的图10.2.，由图可知道，g=5.p=10,q=15比较q和g(p-2)/(g-2)，

将会发现不满足条件q≥g(p-2)/(g-2)，因此Peterson图是不可平面图。

证明：

Petersen图中顶点数p=10，边数q=15，围长g=5

g(p-2)/(g-2)=5*（10-2）/（5-2）=40/3<15=q

不满足9题的结论,所以Peterson图是不可平面图.

11．图11-11是可平面图吗？若是，则请给出平面嵌入，否则说明它是一个包含K5或K3，3的剖分图。

(a） (b）

(c）

图11-11

(d）

分析：存在一个平面嵌入的图是可平面图，因此利用这个定义如果能找到G的一个平面嵌入，则可以判断这个图是可平面图。再由定理11.3.1一个图是可平面图的充分必要条件是该图不包含一个K5或K3，3的剖分图，利用这个定理如果能找到一个图的K5或K3，3的剖分图，则该图不是可平面图。

解：这四个图均是平面图，其平面嵌入分别如下所示：

(a） (b）

(c）

图11-11

(d）

12．平面M上有n条直线将平面M分成若干区域，为了使相互邻接的区域着不同的颜色，最少需要几种颜色？

分析：先将r个区域编成号（如图12-1所示）。

将直线的交点看做图的顶点，所有无限区域的两条无限边都交于一顶点v（等价于所有直线的两端均在无穷远点相交），所得图的示意图为图12-2所示。显然12-2所示的面数与12-1的区域数相同，并且12-1中所示图是区域2-可着色的，当且仅当12-2中所示的图是面2-可着色的。可是12-2是无环的E平面图，利用13题结论可知12-2是面2-可着色的，从而12-1所示的图是区域2-可着色的。

解：最少需要两种颜色。

1

2

6 7

4

5

图12-1

3

6

1

2

7

4

5

3

图12-2

13．设G是一个连通的平面地图，证明*(G)2当且仅当G是欧拉图。

分析：本题的证明利用了图G和其对偶图G*的关系以及第16题的结论：G是二分图当且仅当G*是欧拉图。

又G是点2-可着色的当且仅当G是二分图。因为若G是点2-可着色的，则G中的所有顶点可按着的颜色划分为两个集合，显然着相同颜色的顶点互不邻接，因此这两个集合中的任意两个顶点不邻接，因此G是二分图；反过来，如G是二分图，则G中的所有顶点可划分为两个集合，且每个集合中任意两个顶点不邻接，因此按G的这两个集合将G中所有顶点着两种不同的颜色，是G的正常2着色，因此*(G)2。

证明：设G是一连通的平面地图，则G是一无割边的连通平面图，设G*是G的对偶图，则G*是无环的连通的平面图，因此G是面2-可着色的当且仅当G*是点2-可着色的，而G*是点2-可着色的当且仅当G*是二分图，由题16结论有G*是二分图当且仅当G是欧拉图。

14．将平面分成r个区域，使任意两个区域都相邻，问r最大为多少？

分析：显然当r=1，2，3，4时，可以构造出满足条件的图，如下图是当r=4时满足条件的平面图

f0

f1

f3

f2

因此如果能证明不存在具有5个或5个以上面的平面图，其每两个面都共享一条边。则满足条件的r最大为4。

解：r最大为4。

证明：假设存在这样的平面G，设G的对偶图为G*，则G*也是平面图。由于G至少有5个面，所有G*至少具有5个顶点。设v*为G*的任一顶点，设它位于G的面R中，由于R与其余至少4个面均有公共边，所有v*与其余面中的顶点均相邻，于是d(v*)≥4，而且G*为简单图，于是G*必为Kn(n≥5)，当n=5时，显然K5为非平面图，当n>5时，由于Kn包含一个K5的剖分，所以Kn也不是平面图，这与G*为平面图矛盾。

15．证明：在平面上画有限个圆所得的地图是两色的，即有一个正常2面着色。

分析：本题的证明主要用到了欧拉图的概念和13题的结论，即图G是欧拉图当且仅当G无奇数度的顶点以及G是欧拉图当且仅当(G)2。

*

证明：在平面上画有限个圆所得的地图G显然是一个欧拉图，由13题结论有*(G)2，即G是两色的。

16．设G是平面图，证明：若G是二分图，则G*是欧拉图，又若一个平面图的对偶图是欧拉图，则此平面图是二分图。

分析：该题的证明主要用到了二分图的定义、欧拉图的判定定理及图G的对偶图G*中的顶点的度与G中对应面的次数的关系。即图G是二分图当且仅当G中无奇数长度的回路，而图G是欧拉图当且仅当G无奇数度的顶点。而G*的顶点的度等于图G对应面的次数之和。

证明：设G*是G的对偶图，则G*是连通的，若G是二分图，则G中无奇数长度的回路，因此G*中所有顶点的度数均为偶数，所以G*是欧拉图。

若G*是欧拉图，所以G*中每个顶点的度数都为偶数，所以G中无奇数长度的回路，因此G为二分图。

17．若一个平面图与它的对偶图同构，则称此图是自对偶的，试证明：若G（p,q）是自对偶的，则q=2p-2

分析：由对偶图及同构的定义有：如G（p,q,r）是一个自对偶图，图G*(p*,q*,r*)是它的对偶图，则有p*=r ，q*=q，p=p*,q=q*,r=r*；又因为G是平面图，因此满足欧拉公式p-q+r=2。最后可得q=2p-2。

证明：设G（p,q,r）是一个自对偶图,图G*(p*,q*,r*)是G的对偶图。

则由对偶图的定义有：p*=r q*=q

有G与G*同构，因此有p=p*,q=q*,r=r*

又G是一个平面图，所以p-q+r=2

于是有：2p-q=2 即q=2p-2

18．画一个非简单图的自对偶图。

分析：一个图G的对偶图是按如下方式构造出来的：

在G的每个面f内放上一个顶点f*，这些顶点就构成了G*的顶点集V(G*)，若G的两个面f和g有一条公共边e，则画一条以f*和g*为端点的边e*仅穿过e一次；对于G中属于一个面的割边e，则画一条以f*为端点的环仅穿过e一次。非简单图是有环或重边的图。按照第17题有自对偶图是图G与它的对偶图G*同构的图。由这几方面的定义，可构造如下非简单图的自对偶图。

解：非简单图的自对偶图如下图所示。

G G*


更多推荐

平面图,证明,顶点,欧拉