第7章 圖同構與不變量
7.1 先用不變量排除，再用雙射確認
圖同構是頂點的雙射 f，使任何不同 u、v 都滿足：uv 是原圖的邊，若且唯若 f(u)f(v) 是另一圖的邊。雙射保證頂點不重不漏，「若且唯若」保證邊與非邊都被保留。給了完整邊表時，可逐邊映射並比對得到的邊集合是否恰等於目標邊集合。
改標號或重新畫圖不改圖本身的關係。頂點數、邊數、度數的多重集合、各分量大小、有無三角形，都是同構不變量：例如 f 把 v 的鄰點一一送到 f(v) 的鄰點，故度數相等。只要一項不同，就能否證同構；相同的幾項通常不能證明同構。小圖可用度數縮小候選，最後以雙射與邊集核對。
7.2 四個例題
例題1 相同度數，不同分量
六點環 AB、BC、CD、DE、EF、AF 與兩三角形 AB、BC、AC、DE、EF、DF，都有六點六邊且每點度數 2。前者連通，後者分兩塊；同構保留可達性，所以不同構。
例題2 用雙射交出可核對的證明
G 的邊 AB、BC、CD，H 的邊 AC、AD、BD。取 f(A)=C、f(B)=A、f(C)=D、f(D)=B；映到的邊依次是 AC、AD、BD，恰好整個 H。四個像不同，故為同構。
例題3 一看度數就可否證
四點道路的度數排序是 1、1、2、2；四點星形為 1、1、1、3。有度 3 頂點只在後者，故不用遍歷雙射。
例題4 少檢查非邊會誤判
三點道路 AB、BC 到三角形 AB、BC、AC，恆等映射把原圖每條邊送到邊，但原非邊 AC 成為邊。雖然頂點雙射，仍不是同構。
7.3 練習
- B10-C07-Q01 三角形三頂點重新命名後，會和原圖同構嗎？
- B10-C07-Q02 比較四點圖 AB、BC、CD 與 AC、CD、BD 是否同構。
- B10-C07-Q03 三點道路和三點空圖是否可能同構？
- B10-C07-Q04 兩張四點圖邊數同為 2。一張 AB、BC，另一張 AB、CD。同構嗎？
- B10-C07-Q05 若同構 f 將 A 送到 X，且 A 孤立，X 必孤立嗎？
- B10-C07-Q06 四點環的度數排序？
- B10-C07-Q07 五點道路與三角形加一條分離邊，邊數相同嗎？是否同構？
- B10-C07-Q08 六環和兩個三角形的度數相同，數出各自三角形數。
- B10-C07-Q09 例題2 的映射把非邊 AC 送成什麼？
- B10-C07-Q10 兩張同為連通、同點數且同邊數的圖，必同構嗎？
7.4 完整解答
Q01
會。任一頂點重新命名的雙射都把三個無序點對一一送到三個無序點對；兩圖都是全有邊。
Q02
都是四點道路。依序把第一圖的 A,B,C,D 送到第二圖的 A,C,D,B，邊像為 AC、CD、BD，恰是全邊。
Q03
不可能。前者 2 邊，後者 0 邊；同構會一一對應所有邊。
Q04
前者含一個度 2 頂點和一個孤立點；後者每點度數 1。度數多重集合不同，所以否。
Q05
必然。若 X 有鄰點 Y，由雙射可取 Y 的原像 v，且 v≠A。因 f(A)f(v)=XY 是邊，由同構的逆向條件，Av 必為原圖的邊，與 A 孤立矛盾。
Q06
每個頂點各接環的前後一邊，故排序仍為 2、2、2、2。
Q07
兩者皆 4 邊；道路只有一個分量，另一張有三點和兩點兩個分量，所以不同構。
Q08
六環中每點只有前後兩個鄰點，而這兩個鄰點彼此不相鄰。若有三角形，取其中任一點，另外兩點就必須是它彼此相鄰的鄰點，矛盾。所以六環有 0 個三角形；另一圖每個分量各有 1 個，共 2 個。
Q09
原像 A→C、C→D，故送到 CD，而 H 的邊只有 AC、AD、BD；CD 不是邊。
Q10
不必。四點星形與四點道路都連通且有三邊，但星形的最大度是 3，道路的最大度是 2。