图的同构

图的同构在图论中，图G和H的同构是G和H的顶点集之间的一种双射。.在双射是图对自身的映射的情况下，即当G和H是同一个图时，双射被称为G的自动形态。如果一个图是有限的，我们可以通过证明它是one-one/onto来证明它是双射的；不需要同时证明。图同构是图上的等价关系，因此它把所有图的类划分为等价类。一组互为同构的图形被称为图形的同构类。下面显示的两个图是同构的，尽管它们的图画看起来不同。

在上述定义中，图被理解为无定向的非标记的非加权图。然而，同构的概念可以应用于图的概念的所有其他变体，方法是加入保留相应的额外结构元素的要求：弧的方向、边的权重等，但有以下例外。

对于标记图，有两个同构的定义。根据一个定义，同构是一个既保边又保标的顶点双射。根据另一个定义，同构是一种保边的顶点双投，它保留了标签的等价类，即具有等价（如相同）标签的顶点被映射到具有等价标签的顶点上，反之亦然；边缘标签也一样。{displaystyleK_{2}}图的两个顶点被贴上了标签。图的两个顶点分别标有1和2，在xxx个定义下有一个自动变形，但在第二个定义下有两个自动变形。在某些情况下，当图被赋予xxx的标签时，第二种定义是假定的，这些标签通常取自整数范围1,...,n，其中n是图的顶点数，仅用于xxx地识别顶点。在这种情况下，如果相应的底层非标记图是同构的，那么两个标记图有时被称为同构的（否则同构的定义将是琐碎的）。

同构的正式概念，例如图的同构，抓住了一个非正式的概念，即如果我们忽略有关对象的原子成分的个别区别，一些对象具有相同的结构。每当原子成分（对图来说是顶点和边）的个体性对正确表示图所模拟的任何事物很重要时，模型就会通过对结构施加额外的限制而得到完善，并使用其他数学对象：二维图、标记图、彩色图、有根树等等。同构关系也可以为所有这些图的泛化而定义：同构双射必须保留定义有关对象类型的结构元素：弧、标签、顶点/边缘颜色、有根树的根等。图的同构概念使我们能够区分图的结构本身所固有的图的属性和与图的表示有关的属性：图画、图的数据结构、图的标签等。

例如，如果一个图正好有一个周期，那么其同构类中的所有图也正好有一个周期。另一方面，在常见的情况下，当一个图的顶点是（由）整数1，2，......表示时，则表达式为："N"。N，那么表达式{displaystylesum_{vinV(G)}vcdot{text{deg}}v}。对于两个同构图来说可能是不同的。

由哈斯勒-惠特尼提出的惠特尼图形同构定理指出，当且仅当两个连通的图形的线图是同构的，但有一个例外。K3，三个顶点上的完整图，和完整的二方图K1,3，它们不是同构的，但都以K3为线图。惠特尼图定理可以扩展到超图。

虽然图形同构可以用经典的数学方法研究，如惠特尼定理的例子，但人们认识到这是一个需要用算法方法解决的问题。确定两个有限图是否是同构的计算问题被称为图同构问题。