圖同構

數學敘述

圖同構f:V(G)到V(H)須為雙射，且對所有不同u,v，{u,v}為G的邊當且僅當{f(u),f(v)}為H的邊。只保邊而不保非邊不足。

代表公式（精確 TeX）

I(G,H)

成立條件

• 題庫提供完整有限無向簡單圖邊集合與完整映射表。
• 度數多重集等不變量不符可否證；相同通常不足以證同構。

符號作用域

• I — 圖同構紀錄
• G — 來源圖
• H — 目標圖

直觀、定義與常見誤解

先核映射是雙射。

再核全部無序頂點對的adjacency iff。

不變量匹配只是必要線索，不是一般充分證書。

只比較度數序列或只核原邊映成邊就宣稱同構。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 有限簡單無向圖 — 同構作用於完整有限簡單圖。
• 雙射與唯一原像 — 頂點映射必須一一且覆蓋。
• 二元關係與集合投影 — 鄰接是頂點上的對稱關係。

驗證界線

只分類指定完整有限簡單圖。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入walk、path、連通分量與圖著色。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。