2023年7月19日发(作者：)

作业参考答案——10-特殊图1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是哈密顿图。2.根据给定条件建立一个无向图G=，其中：V={a,b,c,d,e,f,g}E={(u,v)|u,v∈V,且u和v有共同语言}从而图G如下图所示。abcgdef将这7个人围圆桌排位，使得每个人都能与他两边的人交谈，就是在图G中找哈密顿回路，经观察上图可得到两条可能的哈密顿回路，即两种方案：abdfgeca和acbdfgea。3.证明（法一）：根据已知条件，每个结点的度数均为n，则任何两个不相邻的结点vi,vj的度数之和为2n，而图中总共有2n个结点，即deg(vi)+deg(vj)⩾2n，满足哈密顿图的充分条件，从而图中存在一条哈密顿回路，当然，这就说明图G是连通图。证明（法二）：用反证法，假设G不是连通图，设H是G的一个连通分支，由于图G是简单图且每个结点的度数为n，则子图H与G-H中均至少有n+1个结点。所以G的结点数大于等于2n+2，这与G中结点数为2n矛盾。所以假设不成立，从而G是连通图。4.将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G，假设它的互补结点子集V1、V2分别表示n位男士和n位女士，由题意可知V1中的每个结点度1数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。5.此平面图具有五个面，如下图所示。gfar2r1bcr3r4dr5e•r1，边界为abca，D(r1)=3;•r2，边界为acga，D(r2)=3;•r3，边界为cegc，D(r3)=3;•r4，边界为cdec，D(r4)=3;•r5，边界为abcdefega，D(r5)=8;无限面6.设该连通简单平面图的面数为r，由欧拉公式可得，6−12+r=2，所以r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所8∑有面的次数之和D(ri)>3×8=24。但是，已知所有面的次数之和等i=1于边数的两倍，即2×12=24。因此每个面只能由3条边围成。2