资源描述
习 题 十 一1设，证明任何阶图与总有一个是不可平面图。分析： 与是两个互补的图，根据互补的定义，互补的图有相同的顶点数，且G的边数与的边数之和等于完全图的边数p(p-1)/2；而由推论11.2.2，有任何简单平面图G，其顶点数p和边数q满足：q3p-6。 证明. 若与均是可平面图，则 （1） （2）但 （3）将（3）代入（2）有 整理后得 又由（1）有 即 也即 . 得 得此与矛盾。因此任何阶图与不可能两个都是可平面图，从而与总有一个是不可平面图。2证明或否定：两个阶极大简单平面图必同构分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；两个阶极大简单平面图不一定同构。解：令，三个6阶极大简单平面图如下：顶点上标的数字表示该顶点的度，但显然不同构.3找出一个8阶简单平面，使得也是平面图.分析：由第1题证明过程可知，当p11时，和可以同时为平面图。解：如下平面图G，显然其补图也是平面图。4证明或者否定：每个极大平面图是图.分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；而H图是存在一个H回路的图，即存在一条经过图中每一个顶点一次且仅一次的回路。由定理11.1.2知极大平面图的每个面都是三角形，因此G中必存在回路，利用最长回路的性质使用反证法可证明每个极大平面图都是图。证明：设是极大平面而不是图.显然必连通且有回路.设是中最长的回路，由假设，存在不在上且与上和构成一个三方形，于是 从而.矛盾，故是图。5试证明：若平面图的每个面都是三角形，则是极大平面图。分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；利用这个定义使用反证法可证明本题。 证明：设平面图的每个面都是，若不是极大平面图.则中存在，使得，且仍为平面图设是中两个面和的公共边界.于是，中与的面是一个面 ，显然，由此与的每个面都是矛盾.6设是有个分支的平面图，试证明： 分析：由欧拉公式任何简单连通平面图均满足,对G的k个连通利用归纳法使用该结论可证明本题。 证明：当时，即欧拉公式，下设，有个分支. .由欧拉公式有pi-qi+ri=2;但 ，故 即 7证明：是平面图，其中eE（K5）分析：由于 的对称性,只须考虑其中的一条边e，验证是可平面图即可.证明：任选的某条边e，则如下图所示，显然这是一个平面图。8证明：是平面图，其中eE（K3，3）分析：仿照第7题，由于的对称性，因此也只须考虑其中的一条边e，验证是可平面图即可.证明：任选的某条边e，则如下图所示，显然是一个平面图。9一个图的围长是图中最短回路之长度，若图中无回路，则围长定义为无穷大。证明：如果G(p,q,r)是连通平面图，围长g3且有限，则 qg(p-2)/(g-2)分析：由定理11.1.1 对任何平面图，满足 ，又由于G是简单连通图，因此还满足欧拉公式。利用这两个结论可证明本题。证明:由于G的围长为g,故d(fi)g，由定理11.1.1知：可以得到将它代入Euler公式就可以得到qg(p-2)/(g-2)10利用题9证明Peterson图是不可平面图。分析：Petersen图参看书上80页的图10.2.，由图可知道，g=5.p=10,q=15比较q和g(p-2)/(g-2)，将会发现不满足条件qg(p-2)/(g-2)，因此Peterson图是不可平面图。证明：Petersen图中顶点数p=10，边数q=15，围长g=5g(p-2)/(g-2)=5*（10-2）/（5-2）=40/35时，由于Kn包含一个K5的剖分，所以Kn也不是平面图，这与G*为平面图矛盾。 15证明：在平面上画有限个圆所得的地图是两色的，即有一个正常2面着色。分析：本题的证明主要用到了欧拉图的概念和13题的结论，即图G是欧拉图当且仅当G无奇数度的顶点以及G是欧拉图当且仅当。证明：在平面上画有限个圆所得的地图G显然是一个欧拉图，由13题结论有，即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-218画一个非简单图的自对偶图。分析：一个图G的对偶图是按如下方式构造出来的： 在G的每个面f内放上一个顶点f*，这些顶点就构成了G*的顶点集V(G*)，若G的两个面f和g有一条公共边e，则画一条以f*和g*为端点的边e*仅穿过e一次；对于G中属于一个面的割边e，则画一条以f*为端点的环仅穿过e一次。非简单图是有环或重边的图。按照第17题有自对偶图是图G与它的对偶图G*同构的图。由这几方面的定义，可构造如下非简单图的自对偶图。 解：非简单图的自对偶图如下图所示。GG*
展开阅读全文