圖同構
使G的任何兩個頂點U和v在G中相鄰，僅當
下面顯示的兩個圖是同構的，儘管它們的圖紙不同
| 圖G。 | 圖h | 同構 在G和H之間 |
|---|---|---|
 |  | f （ a ）= 1 f （ b ）= 6 f （ c ）= 8 f （ d ）= 3 f （ g ）= 5 f （ h ）= 2 f （ i ）= 4 f （ j ）= 7 |
變化
在上面的定義中，圖表被理解為未指向的非標記的非加權圖。但是，同構的概念可以通過添加要求保留相應的結構附加元素的要求將圖形概念的所有其他變體應用於：弧方向，邊緣權重等，但有以下例外。
標記圖的同構
對於標記的圖，使用了同構的兩個定義。
在一個定義下，同構是一個頂點射擊，既具有邊緣呈現和標籤的貼”。
在另一個定義下，同構是一個具有邊緣的頂點培訓，它保留了標籤的等效類別，即，即具有等效標籤（例如，同一）標籤的頂點，映射到具有等效標籤的頂點上，反之亦然；與邊緣標籤相同。
例如， 
第二個定義是在某些情況下假定的，當圖形賦予了通常從整數範圍1，...， n中獲取的唯一標籤，其中n是圖的頂點的數量，僅用於唯一地識別頂點。在這種情況下，如果相應的未標記圖是同構的，則有時將兩個標記的圖被認為是同構的（否則同構的定義是微不足道的）。
動機
“同構”的形式概念，例如“圖同構”的正式概念，捕獲了非正式的概念，即如果某些對象忽略了所討論的對象的“原子”組件的單個區別，則某些對象具有“相同的結構”。每當“原子”組件的個性（對於圖形的角度和邊緣）對於正確表示由圖形建模的任何內容都很重要時，通過對結構施加其他限制來完善模型，並且使用了其他數學對象：digraphs： digraphs ，標籤圖形圖，彩色圖，生根的樹等。同構之間的關係也可以定義為所有這些圖的概括：同構培養必須保留定義所討論的對像類型的結構元素：弧，標籤，頂點/邊緣顏色，根生樹的根，等。
“圖同構”的概念使我們能夠區分圖形本身結構固有的圖形屬性與與圖形表示相關的屬性：圖形圖，圖形的數據結構，圖形標記等。例如，如果圖完全具有一個週期，然後其同構類別中的所有圖也都有一個週期。另一方面，在圖表的頂點（由）整數1、2，... n的常見情況下，則表達式
對於兩個同構圖可能有所不同。
惠特尼定理
哈斯勒·惠特尼（Hassler Whitney）顯示的惠特尼圖同構定理指出，當且僅當它們的線圖是同構時，兩個連接的圖是同構的，但單個例外： k 3 ，三個頂點上的完整圖，以及完整的bipartite graph k 1 k 1 ，3 ，不是同構，但都具有k 3作為線圖。惠特尼圖定理可以擴展到超圖。
識別圖同構
儘管惠特尼定理（Whitney Theorem）的例證，雖然可以以經典的數學方式研究圖形同構，但人們認識到，使用算法方法可以解決這是一個問題。確定兩個有限圖是否同構的計算問題稱為圖同構問題。
它的實際應用主要包括化學信息學，數學化學（化合物的識別）和電子設計自動化（驗證電子電路設計的各種表示的等效性）。
圖形同構問題是屬於NP的計算複雜性理論中少數標準問題之一，但不知道屬於其眾所周知的任何一個（以及，如果p≠np ，脫節）子集： p和np-complete 。它是Garey＆Johnson（1979）中列出的12個問題中僅有的兩個，其複雜性仍未解決，另一個是整數分解。但是，知道該問題是NP完整的，那麼多項式層次結構將崩潰到有限的水平。
2015年11月，芝加哥大學的數學家和計算機科學家LászlóBabai聲稱已證明了圖形同構問題在準多態時期可以解決。他在2016年的計算理論研討會和2018年國際數學家大會上發表了這些結果的初步版本。 2017年1月，巴貝（Babai）短暫撤回了準多物理主張，並指出了次指數的時間複雜性。五天后，他恢復了原始主張。截至2020年，Babai論文的完整期刊版本尚未出版。
它的概括是子圖同構問題，已知NP完整。
有關該問題的主要研究領域是快速算法的設計以及其計算複雜性的理論研究，無論是針對一般問題還是圖形的特殊類別。
WEISFEILER LEMAN圖同構測試可用於啟發圖同構。如果測試失敗，則保證兩個輸入圖是非同態的。如果測試成功，則圖可能是同構的，也可能不是同構。測試算法的概括可以保證檢測異構，但是它們的運行時間是指數的。