第一章习题
1,对任何简单图 G,(1) 证明：
(1)
()
2
G
υ υ
ε
≤ ； (2)
(1)
()
2
G
υ υ
ε
= 当且仅当 GK
ν
。
2,证明,(1)
,
()
mn
Kmnε = ； (2) 若 G 是完全二部图，则
2
()
4
G
υ
ε ≤ 。
3,图 G 有 21 条边,12 个 3 度顶点，其余顶点的度均为 2，求图 G 的阶数。
4,证明：任何简单图必有至少两个顶点具有相等的度。
5,设 G 是简单图，求 G 的所有不同的生成子图的个数（包括 G 本身和空图） 。
6,证明：任何图中，奇度顶点的个数总是偶数（包括 0） 。并由此证明：在任一次聚会上握过奇数次手的人必为偶数个。
7,证明或反证：如果 u 和 v 是图 G 中仅有的具有奇数度的顶点，则 G 包含一条 u,v 路。
8,证明,若 4υ ≥ 且 1+=νε,则存在 )(GVv∈ 使得 3)( ≥vd 。 由此证明,n 个球队比赛 （ 4n ≥ ）,
已赛完 n+1 场，则必定有一个球队已参加过至少 3 场比赛。
9,在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有 13 个队，能否恰当安排比赛使得每个队在其所在赛区中进行 9 场比赛而与另一个赛区中的运动队进行 4 场比赛？
10,在平面上有 n 个点
12
{,,,}
n
Sxx x=，其中任两个点之间的距离至少是 1。证明在这 n 个点中，
距离为 1 的点对数不超过 3n。
11,某次会议有 n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。
12,在一个化学实验室里，有 n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种化学品恰好在两个药箱中出现，问,（ 1）每个药箱有几种化学品？（ 2）这 n 个药箱中共有几种不同的化学品？
13,在一次舞会中,A,B 两国留学生各 (2)nn> 人,A 国每个学生都与 B 国一些 (不是所有 )学生跳过舞,B 国每个学生至少与 A 国一个学生跳过舞。证明一定可以找到 A 国两个学生
12
,aa及 B
国两个学生
12
,bb，使得
1
a 和
12
,ba和
2
b 跳过舞，而
1
a 和
22
,ba和
1
b 没有跳过舞。
14,证明：
2ε
δ
υ
≤≤Δ,（其中
2ε
υ
称为顶点平均度） 。
15,令 G 是至少有两个顶点的图。证明或反证,(1) 删除一个度为 ()GΔ 的顶点不会增加顶点的平均度； (2) 删除一个度为 ()Gδ 的顶点不会减小顶点的平均度。
16,令 G 是一个顶点平均度为
2
a
ε
υ
= 的无圈图。 (1) 证明,Gx? 的顶点平均度至少为 a 当且仅当
()
2
a
dx≤ 。 (2) 利用 (1)的结果给出一个算法来证明：如果 0a >,则 G 有一个最小度大于
2
a
的子图。
17,如果 2,υ ευ≥<，则连通图 G 至少有两个 1 度顶点。
18,令 u 和 v 是简单图 G 中的相邻顶点。证明,u v 至少属于 G 中的 () () ( )du dv Gυ+? 个三角形。
19,证明含有 n 个顶点的 k 正则图有
2
kn
条边。
20,证明：在 k 度正则图 G 中,)2(mod0≡νk,即正则图的阶数和度数不可能同时为奇数。 （
21,证明：围长为 4 的 k 正则图至少含有 2k 个顶点 ; 围长为 5 的 k 次正则图至少有
2
1k + 个顶。
22,证明：若 ),( EYXG ∪= 是一个 k 度正则二部图，则 |||| YX = 。
23,证明连通图中两条最长路必有公共顶点。
24,若 G 是简单图且 kG ≥)(δ,则 G 有长为至少 k 的路； 如果 2k ≥,则 G 还包含一个长至少为 1k +
的圈。
25,每个无圈图 G 都有一个二部子图至少包含
()
2
Gε
条边。
26,证明,(a) ε ν> 时，图中有圈。 (b) 4ε ν≥+时，图中有两个无公共边的圈。
27,证明：若 G 是
1
()
2
G
υ
δ
≥ 的简单图，则 G 是连通图。 （
28,证明,(a) 若 ()eEG∈,则 () ( ) ()1GGeGω ωω≤?≤ +； （ ()Gω 表示图 G 的连连同分支数） 。
(b) 若 ()vVG∈,则 () ( ) ()1GGvGω ωω≤?≤ +未必成立，试举反例。
29,证明：若 G 是连通图，且每顶皆偶次，则
1
() ()
2
Gv dvω?≤ 。
30,证明或反证：如果 G 是一个 n 顶点简单图，且其最大度是
2
n
、最小度是 1
2
n
，则 G 是连通的。
31,在一电路中,A,B 两点间连接着一电阻，问至少要多少电阻，怎样连接，才能使得任意损坏 9
个电阻时,A 点与 B 点的电路仍连通且不短路？
32,证明 GH? 当且仅当 GH? 。
33,证明：如果图 G 不连通，则其补图 G 必连通。
34,如果图 G 满足 GG?,则称 G 是自补图。证明：若 υ 阶图 G 是自补图，则,(mod)01 4υ = 。
35,一个非连通简单图的补图一定是连通图吗？说明理由。
36,证明 从一个 88× 的方格棋盘中去掉对角的两个小方格后，不能被 12× 和 21× 的矩形覆盖。
37,令 G 是一个 4 顶点图，删除其中的一个点后得到的子图系列如下，试确定 G。
38,下面两图是否同构？
39,讨论下列三个图的同构性
40,证明,Peterson 图与下列图同构
41,已知 n 阶简单图 G 有 m 条边，各顶点的度数均为 3,(1) 若 36mn=?,证明 G 在同构意义下唯一，并求,mn； (2) 若 6n =,证明 G 在同构意义下不唯一。
42 若图 G 有 n 个顶点,1n? 条边，则 G 一定是树吗？说明理由。
43 证明非平凡树中最长路的起点和终点都是叶子（ 1 度点） 。
44 证明恰有两个叶子的树必是路。
45 证明：若 G 是树且 k≥Δ,则 G 至少有 k 个 1 度顶点。
46 证明每个树都是二部图。
47 设
i
n 表示树 T 中度为 i 的顶点的个数。 (1) 证明对非平凡树 T 的叶子数
1
n 有下面公式成立,
1345
3
223 2(2)
i
i
nnnn in
∞
=
=+ + + +=+?
∑
,
d
a
c
b
h
g
f
e
v
1
v
2
v
8
v
7
v
6
v
5
v
4
v
3
u
v
t
s
z
y
x
w
（ 2）证明
1
i
i
in
∞
=
∑
只依赖于树 T 的顶点数。
48 不含圈的图称为森林（ forest）,证明,
（ 1） G 是森林当且仅当 w?=νε ； （ 2）无孤立点的森林至少有 2w 个 1 度顶点。
这里 w 表示 G 的连通分支数，孤立点指零度顶点。
49 证明：具有 m 条边的任意 n 顶点图至少有 1mn? + 个圈。
50 令 T 是一棵 n 顶点数，对于 2 ik≤≤的每个 i 值，树中有一个度为 i 的顶点；其余的 1nk?+个顶点都是叶子。确定 n 并表示成 k 的形式。
51 令 T 是一棵非平凡树，其中所有与叶子相邻的顶点的度至少为 3，证明,T 中某一对叶子有公共的相邻顶点。
52 令 G 是一个连通的 n 顶点图，证明,G 恰有一个圈当且仅当 G 恰有 n 条边。
53 令 T 是一棵树，证明,T 的顶点全为奇度点当且仅当对 ()eET? ∈,Te? 的两个连通分支都具有奇数的阶。
54 令 T 是一棵阶为偶数的树，证明,T 恰有一个生成子图使得其中每个顶点的度均为奇数。
55 证明：若 T 是一个具有 k 条边的树,G 是一个简单图且 ()Gkδ ≥,则 G 含有与 T 同构的子图。
56 令 G 是一棵树，其中 2k 个顶点具有奇数度，证明,G 可分解成 k 条路。
57 对 4n ≥,令 G 是满足 () 2 3Gnε ≥?的简单 n 点图，证明,G 有两个等长的圈。
58 令 u 是连通图 G 的一个顶点，证明不可能选出从 u 到其他各顶点的最短路使得这些路的并是一棵树。
59 令 T,T′是连通图 G 的两棵生成树,对于 () ( )eET ET′∈?,证明存在一条边 () ()eET ET′′∈?，
使得 Tee′′+?和 Tee′? + 都是 G 的生成树。
60 设 G 是一个加权的连通图并且其各边上的权值互不相同。不使用 Kruskal 算法，证明,G 只有一棵权值最小的生成树 （提示：利用上题结论） 。
61 为 n 阶完全图
n
K 的所有边分配整数权值。 假设一个圈的权值是该圈上所有边的权值之和。 证明：
所有圈的权值均为偶数当且仅当具有奇数权值的那些边构成的子图是一个生成二部图。 （提示：
对于具有偶数权值的边构成的子图，其任意连通分量都是一个完全图） 。
62 求下图中从 u
0
到其余各点的最短路。
63 修改 Kruskal 算法用以,
u
0
u
1 u
2
u
3
u
4
u
5
u
6
u
7
1
2
2
2
3
3
1
3
4
4
4
5
6
6
7
7
8
(1) 求赋权连通图中的最大权生成树； （ 2）求不连通赋权图中的最小权生成森林。
64 证明：直径为 k，围长为 21k + 的图是正则图。
65 证明,对任一简单连通图 G 有 rad diam 2radGGG≤ ≤ 。
66 证明,对任意树 T,若只有一个中心,则 diam 2radTT=,若有两个中心,则 diam 2rad 1TT=?,
67 设 G 是一个简单图。证明：若 diam 3G ≥,则 diam 3G ≤ ；若 rad 3G ≥,则 rad 2G ≤ 。
68 证明,若 G 是自补图，则 diam 3G ≤ 。
69 证明：任一非平凡自补图的直径为 2 或 3。
70 设 G 是直径为 2 的简单图，且 2)(?=Δ νG,则 42?≥ νε 。
71 Peterson 图是否二部图？试求其围长、半径、直径。
72 如果 4n ≥,证明直径为 2 且最大度为 n-2 的 n-顶点简单图的最小边数是 2n-4。
73 令 x 和 y 是图 G 中顶点 v 的两个不同的邻点，证明：如果 G 是一棵树，则离心率
2() () ( )ev ex ey≤+。
74 证明树 T 的中心是一个顶点当且仅当 diam 2radTT= 。
75 证明：一棵树要么只有一个重心，要么有两个相邻的重心。 （提示：对相邻顶点 u 和 v，考虑
() ()gu gv? ） 。
76 令 G 是一棵树，它有 n 个顶点,k 个叶子且最大度为 k。 (1) 证明 G 是 k 条具有同一个公共端点的路的并。 (2) 确定 diam G 的可能的最大值和最小值。
77 证明：具有 n+1 条边的任意 n 顶点图的围长最大值为
22
3
n+
。
78 证明：在所有直径为 k 但不是树的图中,21k + 是围长的最大值（提示：证明若 G 有一个长至少为 22k + 的圈，则 G 必有长度更小的圈） 。
79 已知图 G 如下,
（ 1）求 G 的邻接矩阵 A 和关联矩阵 M；
（ 2）求
234
,,AAA，说明从顶点 b 到 d 长度为 1,2,3,4 的路分别有几条。
d
c
b
a
思考题 1,网络会议
某种网络会议系统允许三个地点同时进行网络会议。下图描述的是一个传输网络，
其中圆圈代表客户所在的城市，每条线段两端的客户都可以直接通话。为了让三地同时通话，公司需要激活一些直接连接，使得三个客户端连通。由于激活不同的直接连接的费用不同，公司希望你为它找一个最省钱的激活方式。
例如下图中，为了连接客户 1,4,6，最好的方式是激活加粗的直接连接，总费用是 27,
思考题 2,公平会面
两位外交官处在不同的城市 A 和 B,他们打算请你选择一座城市 X 作为他们会面的地点，并分别为他们制定详细的到达路线。为公平起见，两位外交官行走的路线总长要一样，任何一位外交官不能经过同一座城市两次，并且除了会面地点外，两位外交官不会到达过同一座城市。在这个基础上，你应该使得路线长度最短。假设这样的会面地点和到达路线一定存在。
7
8 4
5
6 2
3
1
6
5
1
7
2
3
9 8
6 4 3
20
1,对任何简单图 G,(1) 证明：
(1)
()
2
G
υ υ
ε
≤ ； (2)
(1)
()
2
G
υ υ
ε
= 当且仅当 GK
ν
。
2,证明,(1)
,
()
mn
Kmnε = ； (2) 若 G 是完全二部图，则
2
()
4
G
υ
ε ≤ 。
3,图 G 有 21 条边,12 个 3 度顶点，其余顶点的度均为 2，求图 G 的阶数。
4,证明：任何简单图必有至少两个顶点具有相等的度。
5,设 G 是简单图，求 G 的所有不同的生成子图的个数（包括 G 本身和空图） 。
6,证明：任何图中，奇度顶点的个数总是偶数（包括 0） 。并由此证明：在任一次聚会上握过奇数次手的人必为偶数个。
7,证明或反证：如果 u 和 v 是图 G 中仅有的具有奇数度的顶点，则 G 包含一条 u,v 路。
8,证明,若 4υ ≥ 且 1+=νε,则存在 )(GVv∈ 使得 3)( ≥vd 。 由此证明,n 个球队比赛 （ 4n ≥ ）,
已赛完 n+1 场，则必定有一个球队已参加过至少 3 场比赛。
9,在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有 13 个队，能否恰当安排比赛使得每个队在其所在赛区中进行 9 场比赛而与另一个赛区中的运动队进行 4 场比赛？
10,在平面上有 n 个点
12
{,,,}
n
Sxx x=，其中任两个点之间的距离至少是 1。证明在这 n 个点中，
距离为 1 的点对数不超过 3n。
11,某次会议有 n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。
12,在一个化学实验室里，有 n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种化学品恰好在两个药箱中出现，问,（ 1）每个药箱有几种化学品？（ 2）这 n 个药箱中共有几种不同的化学品？
13,在一次舞会中,A,B 两国留学生各 (2)nn> 人,A 国每个学生都与 B 国一些 (不是所有 )学生跳过舞,B 国每个学生至少与 A 国一个学生跳过舞。证明一定可以找到 A 国两个学生
12
,aa及 B
国两个学生
12
,bb，使得
1
a 和
12
,ba和
2
b 跳过舞，而
1
a 和
22
,ba和
1
b 没有跳过舞。
14,证明：
2ε
δ
υ
≤≤Δ,（其中
2ε
υ
称为顶点平均度） 。
15,令 G 是至少有两个顶点的图。证明或反证,(1) 删除一个度为 ()GΔ 的顶点不会增加顶点的平均度； (2) 删除一个度为 ()Gδ 的顶点不会减小顶点的平均度。
16,令 G 是一个顶点平均度为
2
a
ε
υ
= 的无圈图。 (1) 证明,Gx? 的顶点平均度至少为 a 当且仅当
()
2
a
dx≤ 。 (2) 利用 (1)的结果给出一个算法来证明：如果 0a >,则 G 有一个最小度大于
2
a
的子图。
17,如果 2,υ ευ≥<，则连通图 G 至少有两个 1 度顶点。
18,令 u 和 v 是简单图 G 中的相邻顶点。证明,u v 至少属于 G 中的 () () ( )du dv Gυ+? 个三角形。
19,证明含有 n 个顶点的 k 正则图有
2
kn
条边。
20,证明：在 k 度正则图 G 中,)2(mod0≡νk,即正则图的阶数和度数不可能同时为奇数。 （
21,证明：围长为 4 的 k 正则图至少含有 2k 个顶点 ; 围长为 5 的 k 次正则图至少有
2
1k + 个顶。
22,证明：若 ),( EYXG ∪= 是一个 k 度正则二部图，则 |||| YX = 。
23,证明连通图中两条最长路必有公共顶点。
24,若 G 是简单图且 kG ≥)(δ,则 G 有长为至少 k 的路； 如果 2k ≥,则 G 还包含一个长至少为 1k +
的圈。
25,每个无圈图 G 都有一个二部子图至少包含
()
2
Gε
条边。
26,证明,(a) ε ν> 时，图中有圈。 (b) 4ε ν≥+时，图中有两个无公共边的圈。
27,证明：若 G 是
1
()
2
G
υ
δ
≥ 的简单图，则 G 是连通图。 （
28,证明,(a) 若 ()eEG∈,则 () ( ) ()1GGeGω ωω≤?≤ +； （ ()Gω 表示图 G 的连连同分支数） 。
(b) 若 ()vVG∈,则 () ( ) ()1GGvGω ωω≤?≤ +未必成立，试举反例。
29,证明：若 G 是连通图，且每顶皆偶次，则
1
() ()
2
Gv dvω?≤ 。
30,证明或反证：如果 G 是一个 n 顶点简单图，且其最大度是
2
n
、最小度是 1
2
n
，则 G 是连通的。
31,在一电路中,A,B 两点间连接着一电阻，问至少要多少电阻，怎样连接，才能使得任意损坏 9
个电阻时,A 点与 B 点的电路仍连通且不短路？
32,证明 GH? 当且仅当 GH? 。
33,证明：如果图 G 不连通，则其补图 G 必连通。
34,如果图 G 满足 GG?,则称 G 是自补图。证明：若 υ 阶图 G 是自补图，则,(mod)01 4υ = 。
35,一个非连通简单图的补图一定是连通图吗？说明理由。
36,证明 从一个 88× 的方格棋盘中去掉对角的两个小方格后，不能被 12× 和 21× 的矩形覆盖。
37,令 G 是一个 4 顶点图，删除其中的一个点后得到的子图系列如下，试确定 G。
38,下面两图是否同构？
39,讨论下列三个图的同构性
40,证明,Peterson 图与下列图同构
41,已知 n 阶简单图 G 有 m 条边，各顶点的度数均为 3,(1) 若 36mn=?,证明 G 在同构意义下唯一，并求,mn； (2) 若 6n =,证明 G 在同构意义下不唯一。
42 若图 G 有 n 个顶点,1n? 条边，则 G 一定是树吗？说明理由。
43 证明非平凡树中最长路的起点和终点都是叶子（ 1 度点） 。
44 证明恰有两个叶子的树必是路。
45 证明：若 G 是树且 k≥Δ,则 G 至少有 k 个 1 度顶点。
46 证明每个树都是二部图。
47 设
i
n 表示树 T 中度为 i 的顶点的个数。 (1) 证明对非平凡树 T 的叶子数
1
n 有下面公式成立,
1345
3
223 2(2)
i
i
nnnn in
∞
=
=+ + + +=+?
∑
,
d
a
c
b
h
g
f
e
v
1
v
2
v
8
v
7
v
6
v
5
v
4
v
3
u
v
t
s
z
y
x
w
（ 2）证明
1
i
i
in
∞
=
∑
只依赖于树 T 的顶点数。
48 不含圈的图称为森林（ forest）,证明,
（ 1） G 是森林当且仅当 w?=νε ； （ 2）无孤立点的森林至少有 2w 个 1 度顶点。
这里 w 表示 G 的连通分支数，孤立点指零度顶点。
49 证明：具有 m 条边的任意 n 顶点图至少有 1mn? + 个圈。
50 令 T 是一棵 n 顶点数，对于 2 ik≤≤的每个 i 值，树中有一个度为 i 的顶点；其余的 1nk?+个顶点都是叶子。确定 n 并表示成 k 的形式。
51 令 T 是一棵非平凡树，其中所有与叶子相邻的顶点的度至少为 3，证明,T 中某一对叶子有公共的相邻顶点。
52 令 G 是一个连通的 n 顶点图，证明,G 恰有一个圈当且仅当 G 恰有 n 条边。
53 令 T 是一棵树，证明,T 的顶点全为奇度点当且仅当对 ()eET? ∈,Te? 的两个连通分支都具有奇数的阶。
54 令 T 是一棵阶为偶数的树，证明,T 恰有一个生成子图使得其中每个顶点的度均为奇数。
55 证明：若 T 是一个具有 k 条边的树,G 是一个简单图且 ()Gkδ ≥,则 G 含有与 T 同构的子图。
56 令 G 是一棵树，其中 2k 个顶点具有奇数度，证明,G 可分解成 k 条路。
57 对 4n ≥,令 G 是满足 () 2 3Gnε ≥?的简单 n 点图，证明,G 有两个等长的圈。
58 令 u 是连通图 G 的一个顶点，证明不可能选出从 u 到其他各顶点的最短路使得这些路的并是一棵树。
59 令 T,T′是连通图 G 的两棵生成树,对于 () ( )eET ET′∈?,证明存在一条边 () ()eET ET′′∈?，
使得 Tee′′+?和 Tee′? + 都是 G 的生成树。
60 设 G 是一个加权的连通图并且其各边上的权值互不相同。不使用 Kruskal 算法，证明,G 只有一棵权值最小的生成树 （提示：利用上题结论） 。
61 为 n 阶完全图
n
K 的所有边分配整数权值。 假设一个圈的权值是该圈上所有边的权值之和。 证明：
所有圈的权值均为偶数当且仅当具有奇数权值的那些边构成的子图是一个生成二部图。 （提示：
对于具有偶数权值的边构成的子图，其任意连通分量都是一个完全图） 。
62 求下图中从 u
0
到其余各点的最短路。
63 修改 Kruskal 算法用以,
u
0
u
1 u
2
u
3
u
4
u
5
u
6
u
7
1
2
2
2
3
3
1
3
4
4
4
5
6
6
7
7
8
(1) 求赋权连通图中的最大权生成树； （ 2）求不连通赋权图中的最小权生成森林。
64 证明：直径为 k，围长为 21k + 的图是正则图。
65 证明,对任一简单连通图 G 有 rad diam 2radGGG≤ ≤ 。
66 证明,对任意树 T,若只有一个中心,则 diam 2radTT=,若有两个中心,则 diam 2rad 1TT=?,
67 设 G 是一个简单图。证明：若 diam 3G ≥,则 diam 3G ≤ ；若 rad 3G ≥,则 rad 2G ≤ 。
68 证明,若 G 是自补图，则 diam 3G ≤ 。
69 证明：任一非平凡自补图的直径为 2 或 3。
70 设 G 是直径为 2 的简单图，且 2)(?=Δ νG,则 42?≥ νε 。
71 Peterson 图是否二部图？试求其围长、半径、直径。
72 如果 4n ≥,证明直径为 2 且最大度为 n-2 的 n-顶点简单图的最小边数是 2n-4。
73 令 x 和 y 是图 G 中顶点 v 的两个不同的邻点，证明：如果 G 是一棵树，则离心率
2() () ( )ev ex ey≤+。
74 证明树 T 的中心是一个顶点当且仅当 diam 2radTT= 。
75 证明：一棵树要么只有一个重心，要么有两个相邻的重心。 （提示：对相邻顶点 u 和 v，考虑
() ()gu gv? ） 。
76 令 G 是一棵树，它有 n 个顶点,k 个叶子且最大度为 k。 (1) 证明 G 是 k 条具有同一个公共端点的路的并。 (2) 确定 diam G 的可能的最大值和最小值。
77 证明：具有 n+1 条边的任意 n 顶点图的围长最大值为
22
3
n+
。
78 证明：在所有直径为 k 但不是树的图中,21k + 是围长的最大值（提示：证明若 G 有一个长至少为 22k + 的圈，则 G 必有长度更小的圈） 。
79 已知图 G 如下,
（ 1）求 G 的邻接矩阵 A 和关联矩阵 M；
（ 2）求
234
,,AAA，说明从顶点 b 到 d 长度为 1,2,3,4 的路分别有几条。
d
c
b
a
思考题 1,网络会议
某种网络会议系统允许三个地点同时进行网络会议。下图描述的是一个传输网络，
其中圆圈代表客户所在的城市，每条线段两端的客户都可以直接通话。为了让三地同时通话，公司需要激活一些直接连接，使得三个客户端连通。由于激活不同的直接连接的费用不同，公司希望你为它找一个最省钱的激活方式。
例如下图中，为了连接客户 1,4,6，最好的方式是激活加粗的直接连接，总费用是 27,
思考题 2,公平会面
两位外交官处在不同的城市 A 和 B,他们打算请你选择一座城市 X 作为他们会面的地点，并分别为他们制定详细的到达路线。为公平起见，两位外交官行走的路线总长要一样，任何一位外交官不能经过同一座城市两次，并且除了会面地点外，两位外交官不会到达过同一座城市。在这个基础上，你应该使得路线长度最短。假设这样的会面地点和到达路线一定存在。
7
8 4
5
6 2
3
1
6
5
1
7
2
3
9 8
6 4 3
20
