^ 1.01.1K.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
^Dushnik, Ben and Miller, Edwin W. Partially ordered sets. American journal of mathematics (JSTOR). 1941, 63 (3): 600–610.
^ 5.05.1LaPaugh, 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
十月 11, 2023
同胚, 圖論, 在圖論中, 同胚, homeomorphism, 是兩個圖之間的一種關係, 指在僅考慮圖分支架構的情況下, 兩圖有相同的分支架構, 在部分情況下, 同胚這個術語亦用於拓樸學中, 互為同胚的兩張圖, 目录, 定義, 計算複雜性, 細分與簡化, 參考文獻定義, 编辑若兩圖g, displaystyle, nbsp, 和g, displaystyle, nbsp, 其中g, displaystyle, nbsp, 是某圖的若干細分變換結果, 且g, displaystyle, nbsp, 可以透過其原像套. 在圖論中 同胚 Homeomorphism 1 2 是兩個圖之間的一種關係 指在僅考慮圖分支架構的情況下 兩圖有相同的分支架構 在部分情況下 同胚這個術語亦用於拓樸學中 3 互為同胚的兩張圖 目录 1 定義 2 計算複雜性 3 細分與簡化 4 參考文獻定義 编辑若兩圖G displaystyle G nbsp 和G displaystyle G nbsp 其中G displaystyle G nbsp 是某圖的若干細分變換結果 且G displaystyle G nbsp 可以透過其原像套用若干細分變換來形成 則稱G displaystyle G nbsp 和G displaystyle G nbsp 同胚 若兩圖的線條 即從一個頂點出發抵達另外一個頂點中途都沒有其他分支的路徑 皆能一一對應 則稱兩圖同胚 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 nbsp 對w套用簡化 或平滑 變換得 nbsp 我們可以再對變換像套用細分變換得 nbsp 而這兩張圖互為同胚 由於互為同胚的兩圖不一定是細分圖關係 可能是其中一張圖要先套用若干次簡化平滑變換後才是細分圖關係 因此 判定兩圖是否同胚 是一個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 amp Hall CRC 2005 ISBN 978 1 58488 505 4 取自 https zh wikipedia org w index php title 同胚 圖論 amp oldid 73907981, 维基百科,wiki,书籍,书籍,图书馆,