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

小提示：

城市 $C$ 和 $E$ 各只连接两条道路，所以它们像 $A$ - $D$ 与 $B$ - $D$ 连接上的绕行。

Cities $C$ and $E$ each touch only two roads, so they behave like detours on the $A$ – $D$ and $B$ – $D$ connections

大提示：

先在化简后的图上数从 $A$ 到 $B$ 的通路，再乘以独立绕行的选择数。

Count the trails from $A$ to $B$ on the reduced graph, then multiply by the independent detour choices

解答：

城市 $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 题