loading中的一条哈密尔顿回路.
8.14 用vi表示颜色i,i?1,2,?,6.做无向图G??V,E?,其中
V?{v1,v2,v3,v4,v5,v6},
E?{(u,v)|u,v?V且u?v,并且u与v能搭配}.
对于任意的v?V,d(v)表示顶点v与别的能搭配的颜色个数,易知G是简单图,且对于任意的u,v?V,均有d(u)?d(v)?3?3?6,由定理8.9可知,G为哈密尔顿图,因而G中存在哈密尔顿回路,不妨设vi1vi2vi3vi4vi5vi6vi1为其中的一条,在这种回路上,每个顶点工表的颜色都能与它相邻顶点代表的颜色相.于是,让vi1与vi2,vi3与vi4,vi5与vi6所代表的颜色相搭配就能织出3种双色布,包含了6种颜色.
8.15
deg(R1)?4,deg(R2)?1,deg(R3)?3,而deg(R0)?12.?deg(Ri)?20?2?10,本图边
i?03数m=10.
分析 平面图(平面嵌入)的面Ri的次数等于包围它的边界的回路的长度,这里所说回路,可能是初级的,可能是简单的,也可能是复杂的,还可能由若干个回路组成.图8.1所示图中,R1,R2,R3的边界都是初级回路,而R0的边界为复杂回路(有的边在回路中重复出现),即e1e2e3e4e5e6e7e8e9e10e1e2e3e4,长度为12,其中边
e5,e6在其中各出现两次.
8.16 图8.11中,实线边所示的图为图8.1中图G,虚线边,实心点图为它的
对偶图的顶点数n*,边数m*,面数r*分别为4,10和8,于是有
分析 从图8.11还可以发现,G的每个顶点位于的一个面中,且的每个面只含G的一个顶点,所以,这是连通平面图G是具有k个连通分支的平面图k?2,则应有r*?n?k?1.读者自己给出一个非连通的平面图,求出它的对偶图来验证这个结论.另外,用图8.1还可以验证,对于任意的v*(G*中的顶点),若它处于G的面Ri中,则应有d(v*)?deg(Ri).
8.17 不能与G同构.
分析 任意平面图的对偶图都是连通的,因而与都是连通图,而G是具有3个连通分支的非连通图,连通图与非连通图显然是不能同构的.
图 8.12 中, 这线边图为图8.2中的图G,虚线边图为G的对偶图,带小杠的边组成的图是G的对偶图,显然G?G.
8.18 因为彼得森图中有长度为奇数的圈,根据定理8.1可知它不是二部图.图中每个顶点的度数均为3,由定8.5可知它不是欧拉图.又因为它可以收缩成
***~K5,由库拉图期基定理可知它也不是平面图.
其实,彼得森图也不是哈密尔顿图图,这里就不给出证明了.
8.19 将图8.4重画在图8.13中,并且将顶点标定.图中afbdcea为图中哈密尔顿回路,见图中粗边所示,所以,该图为哈密尔顿图.
将图中边(d,e),(e,f),(f,d)三条去掉,所得图为原来图的子图,它为K3,3,可取V1?{a,b,c}V2?{d,e,f},由库拉图期基定理可知,该图不是平面图.
8.20 图8.14 所示图为图8.5所示图的平面嵌入.
分析 该图为极大平面图.此图G中,顶点数n?9,边数m?12.若G是不是极大平面图,则应该存在不相邻的顶点u,v,在它们之间再加一条边所得G'还应该是简单平面图, G'的顶点数n'?n?6,m'?n?1?13,于是会有
m'?13?3n'?6?12.
这与定理8.16矛盾,所以,G为极大平面图.
其实,n( n?3)阶简单平面图G为极大平面图当且仅当G的每个面的次数均为3.由图8.14可知,G的每个面的次数均为3,所以,G为极大平面图.
8.12 答案 A,B,C,D全为②
分析 (1) 只有n为奇数时命题为真,见8.11的解答与分析. (2) n?2时,命题为真,见8.11的解答与分析.
(3) 只有n,m都是偶数时,Kn,m中才无奇度数顶点,因而Kn,m为欧拉图,其他情况下,即n,m中至少有一个是奇数,这时Kn,m中必有奇度顶点,因而不是欧拉图.
(4) 只有n?m时, Kn,m中存在 哈密尔顿回路,因而为哈密尔顿图. 当n?m时,不妨设n?m,并且在二部图Kn,m中,|V1|?n,|V2|?m,则
p(G?V1)?m?|V1|?n,这与定理8.8矛盾. 所以, n?m时, Kn,m不是哈密尔顿
图.
8.22 答案 A:②;B②;C②. 分析
图8.15中,两个实边图是同构的,但它们的对偶力(虚边图)是不同构的. (2) 任何平面图的对偶图都是连通图.设G是非连通的平面图,显然有
G?G**.
~
(3) 当G是非连通的平面图时,r*?n?k?1,其中k为G的连通分支数. 8.23 答案 A:④;B②;C②.
分析 根据库期基定理可知,所求的图必含有K5或K3,3同胚子图,或含可收缩成K5或K3,3的子图.由于顶点数和边数均已限定,因而由K3,3加2条边的图可满足要求,由K5增加一个顶点,一条边的图可满足要求,将所有的非同构的简单图画出来,共有4个,其中由K3,3产生的有2个,由K5产生的有2个.见图8.16所示.