# 圖同構

有限簡單圖同構是頂點雙射，對所有頂點對完整保持鄰接與非鄰接。

mko-graph-isomorphism · definition · v0.10.0



## 數學敘述

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





## 代表公式（精確 TeX）

I(G,H)





## 成立條件


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





## 符號作用域


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





## 直觀、定義與常見誤解

先核映射是雙射。

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

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

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





## 已採用的推導導讀

[圖同構：以完整映射表逐項核對雙射與鄰接當且僅當](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-graph-isomorphism-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 同構作用於完整有限簡單圖。
- [雙射與唯一原像](https://ocme.evemisslab.com/zh-Hant/mko/mko-bijective/) — 頂點映射必須一一且覆蓋。
- [二元關係與集合投影](https://ocme.evemisslab.com/zh-Hant/mko/mko-relation/) — 鄰接是頂點上的對稱關係。





## 驗證界線

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

not_formalized

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





## 下一個義務

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





## 同源結構化資料

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

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/graph-isomorphism.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph-isomorphism/index.md)