Question

城市 $A$ 、 $B$ 、 $C$ 、 $D$ 、 $E$ 由道路 $AB$ 、 $AD$ 、 $AE$ 、 $BC$ 、 $BD$ 、 $CD$ 、 $DE$ 连接。有多少条从 $A$ 到 $B$ 的不同路线，可以恰好使用每条道路一次？（这样的路线必然会多次经过某些城市。）

Cities $A,$ $B,$ $C,$ $D,$ and $E$ are connected by roads $AB,$ $AD,$ $AE,$ $BC,$ $BD,$ $CD,$ and $DE.$ How many different routes are there from $A$ to $B$ that use each road exactly once? (Such a route will necessarily visit some cities more than once.)

$7$

$9$

$12$

$16$

$18$

答案：D

知识点：图论分类讨论乘法原理

难度评级：1670

解答：

城市 $E$ （道路 $AE, DE$ ）是在 $A$ - $D$ 旅程上的绕行，城市 $C$ （道路 $BC, CD$ ）是在 $B$ - $D$ 旅程上的绕行。把它们化简后，得到只含 $A, B, D$ 的图，其中有两条 $A$ - $D$ 连接、两条 $B$ - $D$ 连接和一条 $A$ - $B$ 道路。恰好各用一次的 $A$ 到 $B$ 通路有 $4$ 类： $ABDADB$ 、 $ADABDB$ 、 $ADBADB$ 、 $ADBDAB$ 。每个绕行（经 $E$ 、经 $C$ ）都可放在两次经过中的任一次，所以每类给出 $4$ 条实际路线，共 $4\cdot 4 = 16$ 条。正确答案是 D。

City $E$ (roads $AE, DE$ ) is a detour on an $A$ – $D$ trip, and city $C$ (roads $BC, CD$ ) is a detour on a $B$ – $D$ trip. Replace them to get a graph on $A, B, D$ with two $A$ – $D$ connections, two $B$ – $D$ connections, and one $A$ – $B$ road. The trails from $A$ to $B$ using each once are of $4$ types: $ABDADB,$ $ADABDB,$ $ADBADB,$ and $ADBDAB.$ Each detour (through $E,$ through $C$ ) can be taken on either passage, so each type gives $4$ actual routes, for $4\cdot 4 = 16$ routes. Thus, the correct answer is D.

2013 AMC 12B 第 12 题

答案：D

难度评级：1670

解答：

其他年份的第 12 题