第10章 图
且有
?1??0A2??0??0?230001??12???3?00? A??00????000001??11043??12??10??00 A4???0001???0010???64??01? 10??01??(4)(2)由A4中a14D中v1到v4长度为4的路有4条，分别为：e1e1e4e6、e4e6e7e6、e1e2e5e6、?4可知，
e1e3e5e6。
(3)(3)由A3中a11?1可知，D中v1到自身长度为3的回路只有1条，为e1e1e1。
(4)D中长度为4的路总数为
??ai?1j?144(4)ij?16，其中对角元素之和为3，说明长度为4的回路为3条。
(5)D中长度小于等于4的路总数为A、A2、A3、A4中全体元素之和：7＋10＋13＋16＝46，其中回路数为：1＋3＋1＋3＝8。
?4??0234(6)由B4?A?A?A?A??0??0?8148??022?可知，D是单向连通图。
022??022??30.有向图G如图10-52所示，试求： (1)求G的邻接矩阵A。
(2)求出A、A和A，v1到v4长度为1、2、3和4的路有多少？
(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。
解 (1)求G的邻接矩阵为：
?0??0A??0??0?101??011?
101??100??2
3
4
v4v1v3v2图10-52(2)由于
?0??0A2??0??0?111??02??201?3?01A??
02111????02011???12??03??22??044A? ?0312????0101???23??13? 23??22??所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于
9
第10章 图
?0??0ATA??0??0?000??21??312??12TAA? ?21011????10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。
?0??0(4)因为B4?A?A2?A3?A4??0??0?101??0??011??0+
101??0???100???0111??0??201??0+
111??0???011???0212??03??122??04+
212??03???201???0123??13??23??22???0??0?0??0?741??747?，所以
747??434???0??0求可达矩阵为P??0??0?111??111?。
111??111??111??0??111??1∧??1111????111??1000??0??111??0＝??1110????111??0000??111?，所以{v1}，{v2，v3，v4}构成G的强分图。
111??111???0??0(5)因为P?PT??0??0?31.画一个无向欧拉图，使它具有： (1)偶数个顶点，偶数条边。 (2)奇数个顶点，奇数条边。 (3)偶数个顶点，奇数条边。 (4)奇数个顶点，偶数条边。
解 (1)n（n为偶数，且n≥2）阶圈都是偶数个顶点，偶数条边的无向欧拉图。 (2)n（n为奇数，且n≥1）阶圈都是奇数个顶点，奇数条边的无向欧拉图。
(3)在(1)中的圈上任选一个顶点，在此顶点处加一个环，所得图为偶数个顶点，奇数条边无向欧拉图。 (4)在(3)中的圈上任选一个顶点，在此顶点处加一个环，所得图为奇数个顶点，偶数条边无向欧拉图。 32.画一个无向图，使它是： (1)既是欧拉图，又是哈密尔顿图。 (2)是欧拉图，但不是哈密尔顿图。 (3)是哈密尔顿图，但不是欧拉图。 (4)既不是欧拉图，也不是哈密尔顿图。
解 (1)n（n≥3）阶圈，它们都是欧拉图，又是哈密尔顿图。
(2)给定k（k≥2）个长度大于等于3的初级回路，即圈C1，C2?，Ck。将C1中某个顶点和C2中的某个顶点重合，但边不重合，C2中某个顶点和C3中的某个顶点重合，但边不重合，续行此法，直到将Ck?1
10
第10章 图
中某个顶点和Ck中的某个顶点重合，但边不重合，设最后得到的连通图为G，则G是欧拉图，但不是哈密尔顿图。
(3)在n（n≥4）阶圈中，找两个不相邻的顶点，在它们之间加一条边，所得图是哈密尔顿图，但不是欧拉图。
(4)在(2)中的图中，设存在长度大于等于4的圈，比如C1，在C1中找，两个不相邻的顶点，在它们之间加一条边，然后按照（2）的方法构造图G，则G既不是欧拉图，也不是哈密尔顿图。
33.(1)n为何值时，无向完全图Kn是欧拉图？n为何值时，Kn仅存在欧拉路而不存在欧拉回路？ (2)什么样的完全二部图是欧拉图？ (3)n为何值时，轮图Wn为欧拉图？
解 (1)一般情况下，我们不考虑K1。n（n≥2）为奇数时，无向完全图Kn是欧拉图。Kn各结点的度均为n－1，若使Kn为偶拉图，n－1必为偶数，因而必n为奇数。K2仅存在欧拉路而不存在欧拉回路。
(2)设Kr,s为完全二部图，当r、s均为偶数时，Kr,s为欧拉图。
(3)设Wn（n≥4）为轮图，在Wn中，有n－1个结点的度数为3，因而对于任何取值的n（n≥4），轮图Wn都不是欧拉图。
34.证明：完全图K9中至少存在彼此无公共边的两条哈密尔顿回路和一条哈密尔顿通路。
证明 设C1为K9中一条哈密尔顿回路。令G1为K9删除C1中全部边之后的图，则G1中每个结点的度均为6。由定理10.26可知G1仍是哈密尔顿图，因而存在G1中的哈密尔顿回路C2（显然C2也是K9中的哈密尔顿回路，并且C1与C2无公共边）。再L设G2为G1中删除C2中的全部边后所得图，G2为4正则图。由定理10.26可知G2具有哈密尔顿通路。设L为G2中的一条存在哈密尔顿通路，显然C1、C2、L无公共边。
事实上，可以证明在K9中存在4条边不重的哈密尔顿回路。
可以证明：在K3中存在一条边不重合的哈密尔顿回路，K5中存在两条边不重合的哈密尔顿回路，K7
中存在3条边不重合的哈密尔顿回路，一般情况下，K2k+1(k≥1)中最多可存在条边不重合的哈密尔顿回路。
35.已知a、b、c、d、e、f、g 7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？
解 用a、b、c、d、e、f、g 7个结点代表7个人，若两人能交谈（会讲同一种语言），就在代表它们的结点之间连无向边，所得无向图如下图（1），此图中存在哈密尔顿回路：，如图（2）粗边所示，于是按图（3）所示的顺序安排座位即
11
第10章 图
可。
36.证明：对于每个竞赛图D，至多改变一条边的方向后就可以变成哈密尔顿图。
证明 由定理10.26可知D中存在哈密尔顿通路，设D为n（n≥3）阶竞赛图，v1v2?vn为中的一条哈密尔顿通路，若边
237.给定简单无向图G＝
2证明 若n≥Cm?1＋2，则2n≥m－3m＋6 （1）。
2
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝
w?V?d(w)＜m＋(m－2)(m－3)＋m＝m
2
－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。
38.设G是无向连通图，证明：若G中有割点或割边，则G不是哈密尔顿图。
证明 若G中有割点v，则G－{v}中至少有两个连通分支，从而?(G－{v})＞|{v}|，由定理10.25可知，G不是哈密尔顿图。
若G中有割边e，当G只有两个结点时，显然G不是哈密尔顿图。当G的结点数多余2时，从G中删除割边e之后至少有两个连通分支，其中一个连通分支含有割边e的一个端点v且其结点个数大于1，于是?(G－{v})＞|{v}|，由定理10.25可知，G不是哈密尔顿图。
39.某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？
解 可能。依题意，若用结点代表人，两人是朋友时相应结点之间连一条边，则得到一个无向图G＝
由于对任意u、v∈V，有d(u)＋d(v)≥10＋10＝20，根据定理10.26，G为哈密尔顿图，G中存在哈密尔顿回路，按此回路各点位置入席即为所求。
40.设G是具有k(k＞0)个奇数度结点的无向连通图，证明G中边不重合的简单通路的最小数目是它们包含G的全部边。
证明 由握手定理的推论可知，k是偶数。对k做归纳法。 (1)当k＝2时，由定理10.22可知，G中存在偶拉路，结论得证。 (2)设k≤2r（r≥2）时结论成立，要证k为2r＋2时结论成立。
设v1，v2为G中任意二奇度结点，由G的连通性可知，从v1到v2存在路径P0，删除P0上的全部边，得连通分支G1，G2，?，Gs。这些连通分支共含2r个奇度结点，设Gi中含ri个奇度结点，则2ri≤2r（1≤r≤s），且
k，2?2r＝2r。由归纳假设可知，G中存在r条边不重合的简单通路，它们含G中的所有边。
iiiisi?1 12