在圖論中，同胚（）是兩個圖之間的一種關係，指在僅考慮圖分支架構的情況下，兩圖有相同的分支架構。在部分情況下，同胚這個術語亦用於拓樸學中。
定義
若兩圖G和G'，其中G是某圖的若干細分變換結果，且G'可以透過其原像套用若干細分變換來形成，則稱G和G'同胚。若兩圖的線條（即從一個頂點出發抵達另外一個頂點中途都沒有其他分支的路徑）皆能一一對應，則稱兩圖同胚。
計算複雜性
判定兩圖是否同胚是一個NP完全的問題。在與同胚相關的研究中，更常探討的議題是研究某圖的細分是否與另一圖的子圖同構。通常會先假設有2圖，H和G，而大部分文獻的研究著重於H的細分圖是否與G的子圖同構，而若H是一個n頂點的環的話，則這個問題相當於哈密頓迴路問題，因此是一個NP完全的問題。然而，由於不允許對H進行平滑變換，因此上述表述只適用於「若H是沒有任何度為2的頂點的圖，H的細分圖是否與G的子圖同構」，而要證明「H與G是否同胚」問題是一個NP完全問題，可利用簡化的哈密頓迴路問題之小修改來達成：在H和G中每一個與所有其他頂點相鄰的部分加入一個頂點，此時，若G是哈密頓圖時，G所加入的一個頂點會包含與(n + 1)頂點的輪圖同胚之子圖，反之亦然。
參考文獻
#
评论 (0)