同胚 (图论)
在图论中，同胚（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