由AMC10/12難題背景延伸的圖論知識

 A

在2021年AMC12A卷23題（也是AMC10A卷的23題），出現了上圖這樣的問題。雖然在AMC中，沿方格行走的有關(guan) 概率、計數的問題時常出現，但本題使用的新型規則“wrap around”也即在跳到邊上時再跳一步，可以跳到對邊的規則，著實讓許多同學在考場上摸不著頭腦，在AMC10/12的課程中同學們(men) 學習(xi) 過的對稱方法由此失效。

在本題中，由機構馮(feng) 老師提供的方法是比較考驗仔細程度的分步概率方法，也不易在考試時想到；事實上，這樣的問題有強烈的圖論背景，如果大家能夠學會(hui) 把圖形的圖論背景抽象出來，那許多困難的、類似的題目會(hui) 簡單許多。

下麵先給幾個(ge) 定義(yi) ：

Def1

一個(ge) 圖G,是一些頂點(vertex)和邊（edge)構成的集合

如：

從(cong) 以上的定義(yi) 可見，兩(liang) 頂點之間邊的樣式並不重要，我們(men) 隻關(guan) 心他們(men) 之間是否連了邊，以及連了幾條邊

Def2

兩(liang) 頂點V1與(yu) V2相鄰，指它們(men) 之間存在邊，記作V1~V2

頂點V的度（degree)是指與(yu) 它相鄰的頂點個(ge) 數,記作d(v),如②中d(u)=3

Def3

若圖G中有幾個(ge) 頂點，每個(ge) 頂點的度都為(wei) K，則G為(wei) k-regular n-vertex graph

Def4

若圖G中任兩(liang) 個(ge) 頂點V1、V2之間連的邊數不超過1（V1可以等於(yu) V2）稱G為(wei) simple graph

Def5

一條路（path）是一組頂點（V1,V2……VK+1）使Vi~Vi+1,i=1,2,…..k,且i≠j時，Vi≠Vj，定義(yi) path的length為(wei) k,記為(wei) k-path.

定義(yi) path的length為(wei) k,記為(wei) k-path.

Def6

K_n稱為(wei) n階完全圖，即n-vertex graph中，任兩(liang) 個(ge) 頂點都有且僅(jin) 有一條邊

如：

Note: K_n的每個(ge) 頂點為(wei) n-1度

有了以上定義(yi) ，我們(men) 來看一下今年這道AMC12A卷23題（也是AMC10A卷的23題），並嚐試抽象出其圖論性質，我們(men) 將3×3的方格中每一方格看作一個(ge) vertex，並且定義(yi) 兩(liang) 個(ge) vertex x y相鄰if and only if Frieda可以一步從(cong) X走到Y或從(cong) Y走到X這樣，可見本題實際上是個(ge) 9-vertex 4-regular graph

如圖所示：C、A、G、I 為(wei) 題所要求的終點，E為(wei) 起點，現在使用分步求概率就避免了跳躍

也許有同學會(hui) 問，這樣的圖總存在嗎？

比如k-regular n-vertex graph是否總是可以畫在此，

有個(ge) 定理可以回答：

結語：通過簡單的定義(yi) ，希望同學們(men) 學會(hui) 抽象圖論性質簡化問題，明白Erdős-Gallai保證的存在。