同胚 (图论)

若两图${\displaystyle G}$ 和${\displaystyle G'}$ ，其中${\displaystyle G}$ 是某图的若干细分变换结果，且${\displaystyle G'}$ 可以透过其原像套用若干细分变换来形成，则称${\displaystyle G}$ 和${\displaystyle G'}$ 同胚。若两图的线条（即从一个顶点出发抵达另外一个顶点中途都没有其他分支的路径）皆能一一对应，则称两图同胚^[1][4]。

判定两图是否同胚是一个NP完全的问题。在与同胚相关的研究中，更常探讨的议题是研究某图的细分是否与另一图的子图同构。通常会先假设有2图，H和G，而大部分文献的研究着重于H的细分图是否与G的子图同构，而若H是一个n顶点的环的话，则这个问题相当于哈密顿回路问题，因此是一个NP完全的问题。然而，由于不允许对H进行平滑变换，因此上述表述只适用于“若H是没有任何度为2的顶点的图，H的细分图是否与G的子图同构”，而要证明“H与G是否同胚”问题是一个NP完全问题，可利用简化的哈密顿回路问题之小修改来达成：在H和G中每一个与所有其他顶点相邻的部分加入一个顶点，此时，若G是哈密顿图时，G所加入的一个顶点会包含与(n + 1)顶点的轮图同胚之子图，反之亦然^[5]。

细分与简化是图变换的一种，可以用于描述同胚，其中细分与简化互为逆变换。细分是指在边上新增顶点、简化（或平滑）是指将度为2的顶点移除，当一个图套用细分与简化变换后得到的像会与原图同胚，因此不断地套用细分与简化变换在检查图是否同构能判断出两图是否同胚。举例来说，现在有一张图，由两条边组成，分别为e₁ {u,w} 和 e₂ {w,v}

而这两张图互为同胚。由于互为同胚的两图不一定是细分图关系，可能是其中一张图要先套用若干次简化平滑变换后才是细分图关系，因此“判定两图是否同胚”是一个NP完全的问题^[5]。