离散数学期末复习试题及答案
11．若ｕ和ｖ是无向图Ｇ中仅有的两个奇数度顶点，证明ｕ和ｖ是连通的。 可从u 出发，沿着任意条边进入其他顶点，如果已是顶点V，则已
连通。否则，进入某一点后，由于这种点都是偶数度的，能进去一定能 出来， 又进入其他顶点，如果在某一步已进入V，则已连通，不然只 要进入偶次顶点一定又可以出来，由于图中次是有限的，总能到达V。
12．证明 G 是强连通的当且仅当存在一条完备回路。
G 强连通。不妨设顶点为 V1,V2,……,Vn,由强连通，V1 到 V2有 路,V2到 V3有路,……,Vn-1到Vn有路，Vn到V1有路，把这些路连在一 起，是一条完备的回路。
13．证明 G 是单连通的当且仅当存在一条完备道路。?
充分性显然。G 单连通，任一个顶点 V 总能加入到任意有向路中去, 若 G 中某一有向路 C , C:(V1,V2,...,Vi,...,Vm),不含顶点 V， 由单连通性, a C,或 a 到 V 可达,或 V 到 a 可达, 若 V 到 V1可达，则
C1=( V,..., V1,..., Vm), 否则 V1到 V 可达,若 V 到 V2可达,则 C2=( V1,..., V,...,V2,...,Vn), 否则 V2到 V 可达,..., 若 i,Vi到 V 可达,V 到Vi+1可达, 则
Ci+1=(V1,...,Vi,...,V,...,Vi+1,...,Vm),否则均是 V1, V2,……,Vm 到 V 可达, 则
Cm+1＝(V1,...,Vm,...,V), 必可把 V 加入到道路中去。
14．若图 G 中有一顶点V，d(V) = 1，则 G 一定不是哈密顿图。? H 图是存在H 回路的，d(V) = 1, V 不在任何回路上，因此不存在 H 回路。
15．巡回售货员从ａ出发，访问ｂ，ｃ，ｄ，最后回到ａ，求最短路线。?
14
d