同胚 (圖論)
在圖論中，同胚（Homeomorphism）[1][2]是兩個圖之間的一種關係，指在僅考慮圖分支架構的情況下，兩圖有相同的分支架構。在部分情況下，同胚這個術語亦用於拓樸學中[3]。
定義
若兩圖和，其中是某圖的若干細分變換結果，且可以透過其原像套用若干細分變換來形成，則稱和同胚。若兩圖的線條（即從一個頂點出發抵達另外一個頂點中途都沒有其他分支的路徑）皆能一一對應，則稱兩圖同胚[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的頂點移除，當一個圖套用細分與簡化變換後得到的像會與原圖同胚，因此不斷地套用細分與簡化變換在檢查圖是否同構能判斷出兩圖是否同胚。舉例來說，現在有一張圖，由兩條邊組成，分別為e1 {u,w} 和 e2 {w,v}
|
對w套用簡化（或平滑）變換得：
|
我們可以再對變換像套用細分變換得：
|
而這兩張圖互為同胚。由於互為同胚的兩圖不一定是細分圖關係，可能是其中一張圖要先套用若干次簡化平滑變換後才是細分圖關係，因此「判定兩圖是否同胚」是一個NP完全的問題[5]。
參考文獻
- ^ 1.0 1.1 K.Yuvarekha, V.Nandakumar, Dr.P.Sumathi. Characterization of Planar Graph with Edge Series. International Journal of Innovative Research in Science, Engineering and Technology (Department of Mathematics, Bharath University, Chennai, Tamil Nadu, India). 2014-12, 3 (12). ISSN 2319-8753.
Homeomorphism of graph
- ^ 圖同胚 homeomorphism of graph. 國家教育研究院. [2019-05-07]. （原始内容存档于2021-01-19）.
- ^ Hazewinkel, Michiel (编), Homeomorphism, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- ^ Dushnik, Ben and Miller, Edwin W. Partially ordered sets. American journal of mathematics (JSTOR). 1941, 63 (3): 600–610.
- ^ 5.0 5.1 LaPaugh, Andrea S.; Rivest, Ronald L., The subgraph homeomorphism problem, Journal of Computer and System Sciences, 1980, 20 (2): 133–149, MR 0574589, doi:10.1016/0022-0000(80)90057-4
- Yellen, Jay; Gross, Jonathan L., Graph Theory and Its Applications, Discrete Mathematics and Its Applications 2nd, Boca Raton: Chapman & Hall/CRC, 2005, ISBN 978-1-58488-505-4