The Wayback Machine - https://web.archive.org/web/20221025120727/https://baike.sogou.com/kexue/d11016.htm

同胚(图论)

编辑

在图论中,如果存在从G的某个剖分图到G'的某个剖分图的同构,那么两个图G和G'就是同胚的。如果从一个顶点出发到另一个顶点的线条被当做图的边(如它们在示意图中常表示的那样),那么一旦两个图在拓扑结构上是同构的,它们在图论意义上就是彼此同胚的。

1 剖分和平滑编辑

总的来说, 一个图G 的剖分 (有时被称为 扩展[1])是指对G中的边做剖分而得到的图。对某条以{u,v}为顶点的边e做剖分会生成一个图,包含新顶点w 和一组边,其中两条新的边{u,w}和{w,v}替代了边e

例如,边为e,顶点为{u,v }:

可被剖分为两条边,e1e2,连接到一个新顶点 w:

逆向的操作,对顶点w 和与之相连的两条边(e1 ,e2 )做平滑,是指删除连接w 的两条边, 并用一条连接另外两端顶点的新边代替(e1 ,e2 )。需要强调的是,只有度为2的顶点可以被平滑掉。 例如,一个简单的连通图有两条边的图, e1 {u,w }和 e2 {w,v }:

和一个顶点(称为w),顶点可以被平滑掉,生成下面的图:

对图GH 而言,判断H 是否与G 的子图同胚 ,是一个NP-完全问题。[2]

1.1 重心剖分

重心剖分会剖分图的每一条边。这是一种特殊的剖分,因为它总是产生二分图。这个过程可一直重复下去,继而第n个重心剖分就是对图的第n-1个重心剖分做的重心剖分。另外,这样的剖分图始终是简单图。

2 嵌入表面编辑

显然,对一个图做的剖分保留了图的可平面性。库拉托夫斯基(Kuratowski)定理声明

有限图是平面图,当且仅当它不包含与 K 5(有五个顶点的完全图 )或 K 3,3 (有六个顶点的完全二分图 ,其中三个顶点连接到另外三个顶点中的每一个)同胚的子图。

实际上,一个与 K5 或者 K3,3 同胚的图被称为库拉托夫斯基(Kuratowski)子图。

根据罗伯逊-西摩(Robertson–Seymour)定理的推广,可以确定对于每个整数g,存在一组有限的障碍图集  那么当且仅当图H 不包含任何一个  的同胚副本时,H 就可嵌入到亏格为g 的表面上 。例如,  是由库拉托夫斯基(Kuratowski)子图组成。

3 例子编辑

在下面的例子中,图形G和图形H是同胚的。

G

H

如果G'是通过剖分G的外侧边创建的图形,而H'是通过剖分H的内边创建的图形,那么G'和H'具有相同的图形:

G', H'

因此,在G'与H'之间存在同构,这意味着G和H是同胚的。

参考文献

  • [1]

    ^Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 76. ISBN 978-0-486-67870-2. Retrieved 8 August 2012. Definition 20. If some new vertices of degree 2 are added to some of the edges of a graph G, the resulting graph H is called an expansion of G..

  • [2]

    ^The more commonly studied problem in the literature, under the name of the subgraph homeomorphism problem, is whether a subdivision of H is isomorphic to a subgraph of G. The case when H is an n-vertex cycle is equivalent to the Hamiltonian cycle problem, and is therefore NP-complete. However, this formulation is only equivalent to the question of whether H is homeomorphic to a subgraph of G when H has no degree-two vertices, because it does not allow smoothing in H. The stated problem can be shown to be NP-complete by a small modification of the Hamiltonian cycle reduction: add one vertex to each of H and G, adjacent to all the other vertices. Thus, the one-vertex augmentation of a graph G contains a subgraph homeomorphic to an (n + 1)-vertex wheel graph, if and only if G is Hamiltonian. For the hardness of the subgraph homeomorphism problem, see e.g. LaPaugh, Andrea S.; Rivest, Ronald L. (1980), "The subgraph homeomorphism problem", Journal of Computer and System Sciences, 20 (2): 133–149, doi:10.1016/0022-0000(80)90057-4, MR 0574589..

阅读 1322
版本记录
  • 暂无