如果兩個圖包含相同數量的圖頂點，且以相同方式連線，則稱它們是同構的。形式上，如果存在 置換 
of 
使得 
在 圖邊 的集合 
中 當且僅當 
在 圖邊 的集合 
中，則具有 圖頂點 
的兩個圖 
和 
被稱為是同構的。
規範標記是用於確定圖同構的一種實用有效技術。有幾種軟體實現可用，包括 nauty (McKay)、Traces (Piperno 2011; McKay and Piperno 2013)、saucy 和 bliss，其中後兩者特別針對大型稀疏圖。
可以使用 Wolfram 語言中的以下命令來確定兩個圖的等價性或不等價性IsomorphicGraphQ[g1, g2].
確定兩個圖是否同構被認為既不是 NP 完全問題 也不是 P 問題，儘管這尚未得到證明 (Skiena 1990, p. 181)。事實上，有一個著名的複雜度類叫做圖同構完備，它被認為與 NP 完全 和 P 完全不相交。
然而，對於平面圖（Hopcroft 和 Tarjan 1973，Hopcroft 和 Wong 1974）以及當最大頂點度受常數限制時（Luks 1982；Skiena 1990，p. 181），已知存在多項式時間演算法。
在某種意義上，圖同構在實踐中很容易，除了一組病態的困難圖似乎引起所有問題之外。因此，與結理論不同，從未出現過任何同構性未解決的重要圖對。事實上，多年來，化學家一直在尋找一種易於計算的不變數，它可以區分代表分子的圖。有整系列的論文，其中一位作者提出了一些不變數，另一位作者提供了一對該不變數無法區分的圖，等等。不幸的是，幾乎肯定沒有簡單的可計算的通用圖不變數，無論是基於圖譜還是圖的任何其他引數（Royle 2004）。
演算法。" J. Comput. Sys. Sci. 7, 323-331, 1973.Hopcroft, J. E. and Wong, J. K. "平面圖同構的線性時間演算法（初步報告）。" In STOC '74: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. New York: ACM, pp. 172-184, 1974.Junttila, T. A. and Kaski, P. "bliss."