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

解答：

将上排四座城市依次命名为 $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}$ 两个 $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 题