2019 AMC 12B 第 10 题

Question

下图是一张地图，显示

12

座城市和连接某些城市对的

17

条道路。Paula 想从城市

A

出发，到城市

L

结束，恰好走过其中

13

条道路，且任何一段道路都不能走超过一次。（Paula 可以多次到访同一座城市。）Paula 有多少条不同路线可以选择？

The figure below is a map showing

12

cities and

17

roads connecting certain pairs of cities. Paula wishes to travel along exactly

13

of those roads, starting at city

A

and ending at city

L,

without traveling along any portion of a road more than once. (Paula is allowed to visit a city more than once.) How many different routes can Paula take?

0

1

2

3

4

答案：E

知识点：图论奇偶性分类讨论

难度评级：1640

小提示：

用掉

17

条道路中的

13

条，正好留下

4

条不用

Using

13

of the

17

roads leaves exactly

4

roads unused

大提示：

只有当仅

A

和

L

的度数为奇数时才存在这样的迹；这会强制决定要删掉哪

4

条道路

A trail exists only if just

A

and

L

have odd degree; this forces which

4

roads to drop

解答：

将上排四座城市依次命名为

A,B,C,D

，中排为

E,F,G,H

，下排为

I,J,K,L

。一条使用

13

条道路的路线是一条开放欧拉迹，所以在所用道路构成的图中，只有

A

和

L

的度数为奇数。

在完整地图中，需要改变度数奇偶性的顶点是

A,B,C,E,H,J,K,L

。因为只删除

4

条道路，这四条道路必须将这

8

个顶点两两配对。其中

E

只与

A

相邻，所以必须删除

AE

；随后

BC

也被迫删除。同理，

H

只与

L

相邻，所以必须删除

HL

，随后删除

JK

。

剩余图是一条链

\begin{gathered} A-B-F,\\ F-E-I-J-F,\\ F-G,\\ G-C-D-H-G,\\ G-K-L \end{gathered}\text{。}

两个

4

边形环各可沿两个方向遍历，其余部分都被迫确定。因此共有

2\cdot2=4

条路线。

所以 E 是正确答案。

Name the four cities in the top row

A,B,C,D,

those in the middle row

E,F,G,H,

and those in the bottom row

I,J,K,L.

A route using

13

roads is an open Euler trail, so in the used graph exactly

A

and

L

have odd degree.

In the full map, the vertices whose degree parity must change are

A,B,C,E,H,J,K,L.

Because only

4

roads are removed, those roads must pair these

8

vertices. Among them,

E

is adjacent only to

A,

forcing

AE

to be removed; then

BC

is forced. Similarly

H

is adjacent only to

L,

forcing

HL,

and then

JK.

The remaining graph is a chain

\begin{gathered} A-B-F,\\ F-E-I-J-F,\\ F-G,\\ G-C-D-H-G,\\ G-K-L. \end{gathered}

Each of the two

4

-cycles can be traversed in either direction, and everything else is forced. Hence there are

2\cdot2=4

routes.

Thus, E is the correct answer.

2019 AMC 12B 第 10 题

答案：E

难度评级：1640

小提示：

大提示：

解答：

其他年份的第 10 题