《离散数学》课件 第11章 平面图.ppt

习题11.17设G是n(n≥7)阶外平面图，证明G不是外平面图。证明：只需验证n=7的极大平面图G的补图G不是外平面图即可。7阶极大外平面图的平面嵌入为5个K2和一个长为7的圈围成，在同构意义下只有(a)(b)(c)(d)4种情况。(e)(f)(g)(h)分别为它们的补图，这4个补图都是平面图，由定义判断它们不是外平面图。图(i)(j)(k)(l)分别为图(e)(f)(g)(h)的平面嵌入，易知它们不是外平面图。习题11.18证明《教程》中图11.17(b)是哈密顿图，但不存在既含边e1又含边e2的哈密顿回路。证明：易知图中e3e15e14e13e12e2e7e8e9e10为一条哈密顿回路，所以该图是哈密顿图。反证法证明不存在含边e1和e2的哈密顿回路。否则，则e3必在这条哈密顿回路C中(否则e10,e15,e6,e11均在C上，与e1,e2形成6阶圈)。e10,e15不能同时在C上，e6,e11也不能同时在C上。为了保证a,f顶点在C上是2度顶点，必有e10和e11或e6和e15在C上。假设e10和e11在C上，此时顶点e和g在C上是2度顶点，所以边e9和e12不在C上，必有e14和e7在C上，又由于e12不在C上，必有e4和e13在C上，此时点d不能在C上(e3e10e1e14e13e4e7e2e11已成圈)，矛盾。*8.4证明：证明（续）：8.7证明下面的两个图都不是哈密顿图。证明：先证明a不是哈密顿图利用定理8.6，即证明此图破坏哈密顿图应满足的必要条件.取顶点集的子集V1={a,b,c,d,e}，则p(G-V1)=7|V1|=5,由定理8.6知，右图不是哈密顿图证明（续）：证明b不是哈密顿图：利用定理8.6：V1={a,b,c,d,e,f}p(G-V1)=7|V1|=68.13证明：证明（续）：习题9.2无向树T有9片树叶，3个3度顶点，其余顶点的度数均为4，问T中有几个4度顶点？根据T的度序列，你能画出多少棵非同构的无向树？解答应用握手定理和树的性质，求解无向树.设有x个4度顶点，则阶数n=x+9+3=12+x,m=n-1,由握手定理，2m=22+2x=9+3×3+4x，得到x=2即有2个4度顶点，于是所求树均为14阶树，度序列为1，1，1，1，1，1，1，1，1，3，3，3，4，4下面按直径为6，5，4分别给出非同构的树，共14种解答（续1）：直径为6的树解答（续2）直径为5和4的树（最后一个直径为4）9.69.1110.2利用基本关联矩阵法求下图的所有生成树v1v2v3v4v5e5e1e4e2e6e310.2解答利用定理10.3求解图G的关联矩阵如下10.2解答（续1）：以v5为参考点，写出基本关联矩阵10.2解答（续2）：10.2解答（续3）计算出所有的行列式，其中，两个行列式为0，其余8个行列式均非0，对应G的生成树。G的所有生成树如下：10.4有向图D如右图所示.D中v1到v4长度为1,2,3,4的通路各为多少条？v1到v4长度小于等于3的通路为多少条？v1到v1长度为1,2,3,4的回路各为多少条？v4到v4长度小于等于3的回路为多少条？D中长度为4的通路（不含回路）有多少条？D中长度为4的回路有多少条？D中长度小于等于4的通路为多少条？其中多少条为回路？写出D的可达矩阵。10.4解答只需计算有向图D的邻接矩阵A及A2,A3,A410.4解答（续1）为计算方便，还可以计算出B1,B2,B3,B410.4解答（续2）根据上述计算，可以得到D中v1到v4长度为1,2,3,4的通路分别为0,0,2,2条v1到v4长度小于等于3的通路为2条v1到v1长度为1,2,3,4的回路分别为1,1,3,5条v4到v4长度小于等于3的回路为1条D中长度为4的通路（不含回路）有33条D中长度为4的回路有11条D中长度小于等于4的通路为88条,其中22条为回路D的可达矩阵为全1矩阵，即为强连通图。习题11.6设G为n阶m条边的简单连通平面图，证明：当n=7,m=15时G为极大平面图。证明：用极大平面图的定义证。由于n=7,m=15,G不可能为完全图，因而存在不相邻的顶点u,v,设G’=G?(u,v)，则G’是n’=7,m’=16的无向简单图，但G’已不是平面图。如果G’为平面图，根据定理11.10，应有m’≤3n’-6(16≤21-6=15)，这个是矛盾。所以G’不是平面图，根据定义，G为极大平面图。习题11.7设G是n(n≥11)阶无向简单图，证