2024年1月7日发(作者：打印数学试卷怎么没符号)

习题十一

1. 设p>ll，证明任何卩阶图G与厂总有一个是不可平面图。

分析：G与厂是两个互补的图，根据互补的定义，互补的图侑相同的顶点数，且G的边数与厂 的边数Z和等于完全图的边数p(p-l)/2；而由推论1122,有任何简单平面图G,其顶点数p和边 数q满足：qW3p-6。

证明.若G(p,g)与石(p：q、均是可平面图，贝ij

q <3p -6

fq <3p\' -6

但

p=p ,qp( p-)-q

将(3)代入(2)有一p(p_l)_g<3p-6

2

整理后得I，Tp + 252q

即

也即

2

13-V73

乂山⑴有

/72-7p + 12<2(3/;-6)

p2 -13/7+ 24 <0

13-J132-4x24

13+Jl 32—4x24

(1)

(2)

(3)

2

13 + V73

------- < p< -----------

2 2

得 2 < /? < 11

此与p>才盾。

因此任何\"阶图G与E不可能两个都是可平而图，从而G与X总有一个是不可平而图。

2. 证明或否定：两个卩阶极人简单平面图必同构

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

一定同构。

解：令° = 6,三个6阶极大简单平面图GPG2,G3如下:

G,

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

3. 找出一个8阶简单平而G,使得G也是平而图—

分析：由第1题证明过程可知，当p

解:如下平面图G,显然其补图也是平面图。

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

分析：极人平而图是指添加任何一条边以麻不构成平而图的平而图；而H图是存在一个H冋路的

图，即存在一条经过图中每一个顶点一次且仅一次的回路。由定理11丄2知极人平而图的每个面

都是三角形，因此<3小必存在回路，利用最长回路的性质使用反证法可证明每个极大平面图都是

丹图。

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

设c是G中最长的回路c =

UV2--VHU ,由假设, 存在VV 6 v(G)不在C上且W与C上片和v/+1构

成一个三方形，于是

C

-匕 VV 片+1

\'\'\'VnUVV2 • •

• V,

=WVj . ••片 W匕+1 ・…

从而c>c.矛盾,故G是H图。

V2

5. 试证明：若平面图G的每个面都是三角形心，则G是极人平面图。

分析：极人平面图是指添加任何一条边以后不构成平血图的平面图；利用这个定义使用反证

法可证明本题。

证明：设平面图G的每个面都是心，若G不是极人平面图.则G中存在V(G),使得

uv^ E(G),且G + uv仍为平面图

设3是G + uv中两个面和/；的公共边界.于是，G中与力的面是一个面厶，显然 d(/Q>3,由此与G的每个面都是他矛盾.

6. 设G(p,q,0是有R个分支的平面图，试证明:

p - q-- r = k +

分析：由欧拉公式任何简单连通平面图G(p, q, r)均满足p—q+r=2，对G的k个连通利用归纳

法使用该结论可证明木题。

证明：当比=1吋，即欧拉公式，下设k>2, G有比个分支.

G| (卩|,如，耳…,G&•(几，么，q ).由欧拉公式有Pi-qi+ip2;

但工Pi= p，Di=q，口 =r + k-i

i=l i=l

故

p-q + r + k — l = 2k

即

p-q+r=k+l

z=l

7. 证明：k5-e是平面图，其中eeE (K5)

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

证明：任选也的某条边e,则忍-丘如下图所示，显然这是一个平而图。

8. 证明：k3,3-e是平面图，其中e£E(K3・3)

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

图即可.

证明：任选也.3的某条边C,贝％3.3-£如下图所示，显然是一个平面图。

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

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

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

工d(fj=2q ,又由于G是简单连通图， 因此还满足欧拉公式p-q+r=2 o利用这两个结论可证明本题。

证明:由于G的围长为g,故d(fj)^g,由定理11.1.1知:

gr<^d(fi)=2q

i=

可以得到r<2q/g

将它代入Euler公式就可以得到qWg(p>2)/(g・2)

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

分析：Petersen图参看书上80页的图102,由图可知道,g=5.p=10,q=15比较q和g(p-2)/(g-2), 将会发现不满足条件q2g(p-2)/(g-2),因此Peterson图是不可平而图。

证明：

Petersen图11〔顶点数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是可平面图吗？若是，则请给出平面嵌入，否则说明它是一个包含氐或心3的剖分

图。

)/

图11・11

分析：存在一个平而嵌入的图是可平而图，因此利用这个定义如果能找到G的一个平而嵌入，则

可以判断这个图是可平面图。再由定理1131 —个图是可平面图的充分必要条件是该图不包含一 个K5或K, 3的剖分图，利用这个定理如果能找到一个图的g或K, 3的剖分图，则该图不是可 平面图。

解：这四个图均是平而图，其平而恢入分别如卜•所示：

(a

丿

(c)

厂、y

图 11-11

(d)

12. 平而M上有n条总线将平而M分成若干区域，为了使相互邻接的区域着不同的颜色，最少

需要儿种颜色？

分析：先将「个区域编成号（如图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 ■可着色的。

解：最少需要两种颜色。

13. 设G是一个连通的平面地图，证明^(G)=2当且仅当G是欧拉图。

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

G*是欧拉图。

乂 G是点2-可着色的当且仅当G是二分图。因为若G是点2-可着色的，则G中的所有顶

点可按着的颜色划分为两个集合，显然着相同颜色的顶点互不邻接，因此这两个集合屮的任意两 个顶点不邻接，因此G是二分图；反过來，如G是二分图，则G中的所冇顶点可划分为两个集 合，且每个集合中任意两个顶点不邻接，因此按G的这两个集合将G中所有顶点着两种不同的颜 色，是G的正常2着色，因此Z*(G)=2o

证明：设G是一•连通的平面地图，则G是一无割边的连通平面图，设G*是G的对偶图，则G*

是无环的连通的平面图，因此G是面2」J着色的当R仅当G*是点2■口J着色的，而G*是点2■可着 色的当且仅当G*是二分图，由题16结论有G*是二分图当一口•仅当G是欧拉图。

14. 将平面分成「个区域，使任意两个区域都相邻，问「最人为多少？

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

fl

fa

f2

因此如果能证明不存在具有5个或5个以上血的平面图，其每两个面都共享一•条边。则满足条件 的I•授大为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是欧拉图当R仅当G无奇数

度的顶点以及G是欧拉图当且仅当力*

(G)=2 o

证明：在平血上画有限个圆所得的地图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. 若一个平面图与它的对偶图同构，贝0称此图是B对偶的，试证叽若G (p,q)是自对偶的，

则 q=2p-2

分析：由对偶图及同构的定义冇：如G(p,q,r)是一个自对偶图，图G*(p*,q*,严)是它的对偶图，

则有p*=r , q*=q, p=p*,q=q*,r=r*；又因为G是平面图，因此满足欧拉公式p-q+r=2。戢后「】J得

q=2p-2o

证明：设G (p,q,r)是一个B对偶图，图G*(p%q0*)是G的对偶图。

则由対偶图的定义有:p*=r q *=q

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

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

于是有：2p-q=2 U|J q=2p-2

18. 烦一个非简单图的白对偶图。

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

在G的每个而f内放上一个顶点f*,这些顶点就构成了 G*的顶点集V(G*),若G的两个而f 和g有一条公共边e,则画一•条以f*和g*为端点的边e*仅穿过e 一次；对于G中属于一个而的割

边e,贝IJ画一条以f*为端点的环仅穿过e—次。非简单图是有环或重边的图。按照第17题有白对

偶图是图G与它的对偶图G*同构的图。由这几方面的定义，可构造如下非简单图的白对偶图。

解：非简单图的白对個图如下图所示。


更多推荐

证明,顶点,平面图