text: 在圖論中，同胚是兩個圖之間的一種關係，指在僅考慮圖分支架構的情況下，兩圖有相同的分支架構。在部分情況下，同胚這個術語亦用於拓樸學中。定義.若兩圖formula_1和formula_2，其中formula_1是某圖的若干細分變換結果，且formula_2可以透過其原像套用若干細分變換來形成，則稱formula_1和formula_2同胚。若兩圖的線條皆能一一對應，則稱兩圖同胚。計算複雜性.判定兩圖是否同胚是一個NP完全的問題。在與同胚相關的研究中，更常探討的議題是研究某圖的細分是否與另一圖的子圖同構。通常會先假設有2圖，H和G，而大部分研究著重於H的細分圖是否與G的子圖同構，而若H是一個n頂點的環的話，則這個問題相當於哈密頓迴路問題，因此是一個NP完全的問題。然而，由於不允許對H進行平滑變換，因此上述表述只適用於「若H是沒有任何度為2的頂點的圖，H的細分圖是否與G的子圖同構」，而要證明「H與G是否同胚」問題是一個NP完全問題，可利用簡化的哈密頓迴路問題之小修改來達成：在H和G中每一個與所有其他頂點相鄰的部分加入一個頂點，此時，若G是哈密頓圖時，G所加入的一個頂點會包含與(n + 1)頂點的輪圖同胚之子圖，反之亦然。細分與簡化.而這兩張圖互為同胚。由於互為同胚的兩圖不一定是細分圖關係，可能是其中一張圖要先套用若干次簡化平滑變換後才是細分圖關係，因此「判定兩圖是否同胚」是一個NP完全的問題。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 同胚 (圖論)
metadata: https://zh.wikipedia.org/wiki?curid=6575217