查看“︁同胚 (圖論)”︁的源代码

{{Double image|right|Graph homeomorphism example 1.svg|120|Graph homeomorphism example 2.svg|120|互為同胚的兩張圖。}}
在[[圖論]]中，'''同胚'''（{{lang|en|Homeomorphism}}）<ref name="K.Yuvarekha 2014">{{Cite journal
  |title=Characterization of Planar Graph with Edge Series
  |author=K.Yuvarekha, V.Nandakumar, Dr.P.Sumathi
  |journal=International Journal of Innovative Research in Science, Engineering and Technology
  |volume=3
  |number=12
  |ISSN=2319-8753 
  |date=2014-12
  |publisher=Department of Mathematics, Bharath University, Chennai, Tamil Nadu, India
  |quote=Homeomorphism of graph}}</ref><ref>{{Cite Web | url = http://terms.naer.edu.tw/detail/2117252/?index=7 | title = 圖同胚 homeomorphism of graph | website = [[國家教育研究院]] | accessdate = 2019-05-07 | archive-date = 2021-01-19 | archive-url = https://web.archive.org/web/20210119093853/http://terms.naer.edu.tw/detail/2117252/?index=7 }}</ref>是兩個[[圖 (圖論)|圖]]之間的一種關係，指在僅考慮圖分支架構的情況下，兩圖有相同的分支架構。在部分情況下，[[同胚]]這個術語亦用於[[拓樸學]]中<ref>{{springer|title=Homeomorphism|id=p/h047600}}</ref>。

== 定義 ==
若兩圖<math>G</math>和<math>G'</math>，其中<math>G</math>是某圖的若干[[細分 (圖論)|細分變換]]結果，且<math>G'</math>可以透過其[[原像 (幾何)|原像]]套用若干細分變換來形成，則稱<math>G</math>和<math>G'</math>同胚。若兩圖的線條（即從一個[[顶点 (图论)|頂點]]出發抵達另外一個頂點中途都沒有其他分支的路徑）皆能一一對應，則稱兩圖同胚<ref name="K.Yuvarekha 2014"/><ref name="articledushnik1941partially">{{Cite journal
  |title=Partially ordered sets
  |url=https://archive.org/details/sim_american-journal-of-mathematics_1941-07_63_3/page/600
  |author=Dushnik, Ben and Miller, Edwin W
  |journal=American journal of mathematics
  |volume=63
  |number=3
  |pages=600-610
  |year=1941
  |publisher=JSTOR}}</ref>。

== [[計算複雜性理論|計算複雜性]] ==
判定兩圖是否同胚是一個[[NP完全]]的問題。在與同胚相關的研究中，更常探討的議題是研究某圖的細分是否與另一圖的子圖同構。通常會先假設有2圖，H和G，而大部分文獻的研究著重於H的細分圖是否與G的子圖同構，而若H是一個n頂點的環的話，則這個問題相當於[[哈密頓迴路]]問題，因此是一個NP完全的問題。然而，由於不允許對H進行平滑變換，因此上述表述只適用於「若H是沒有任何度為2的頂點的圖，H的細分圖是否與G的子圖同構」，而要證明「H與G是否同胚」問題是一個NP完全問題，可利用簡化的哈密頓迴路問題之小修改來達成：在H和G中每一個與所有其他頂點相鄰的部分加入一個頂點，此時，若G是哈密頓圖時，G所加入的一個頂點會包含與(n + 1)頂點的輪圖同胚之子圖，反之亦然<ref name="Andrea S.LaPaugh 1980"/>。

== 細分與簡化 ==
{{main|细分 (图论)|平滑 (圖論)}}
[[细分_(图论)|細分]]與[[平滑 (圖論)|簡化]]是圖變換的一種，可以用於描述同胚，其中細分與簡化互為逆變換。細分是指在邊上新增頂點、簡化（或平滑）是指將度為2的頂點移除，當一個圖套用細分與簡化變換後得到的像會與原圖同胚，因此不斷地套用細分與簡化變換在檢查圖是否同構能判斷出兩圖是否同胚。舉例來說，現在有一張圖，由兩條邊組成，分別為''e''<sub>1</sub> {''u'',''w''} 和 ''e''<sub>2</sub> {''w'',''v''}
{| class="wikitable" 
|align=center|<br/>[[Image:Graph subdivision step2.svg|150px]]
|align=center|對w套用簡化（或平滑）變換得：<br/>[[Image:Graph subdivision step1.svg|150px]]
|align=center|我們可以再對變換像套用細分變換得：<br/>[[Image:Graph subdivision step2.svg|150px]]
|}
而這兩張圖互為同胚。由於互為同胚的兩圖不一定是細分圖關係，可能是其中一張圖要先套用若干次簡化平滑變換後才是細分圖關係，因此「判定兩圖是否同胚」是一個NP完全的問題<ref name="Andrea S.LaPaugh 1980">{{citation
 | last1 = LaPaugh | first1 = Andrea S.
 | last2 = Rivest | first2 = Ronald L.
 | doi = 10.1016/0022-0000(80)90057-4
 | issue = 2
 | journal = Journal of Computer and System Sciences
 | mr = 574589
 | pages = 133–149
 | title = The subgraph homeomorphism problem
 | volume = 20
 | year = 1980}}</ref>。

==參考文獻==
{{refbegin|2}}
{{reflist}}
#{{Citation | last1=Yellen | first1=Jay | last2=Gross | first2=Jonathan L. | title=Graph Theory and Its Applications | location=Boca Raton| publisher=Chapman & Hall/CRC | edition=2nd | series=Discrete Mathematics and Its Applications | isbn=978-1-58488-505-4 | year=2005}}
{{refend}}

[[Category:图论]]