在图论中,如果存在从G的某个剖分图到G'的某个剖分图的同构,那么两个图G和G'就是同胚的。如果从一个顶点出发到另一个顶点的线条被当做图的边(如它们在示意图中常表示的那样),那么一旦两个图在拓扑结构上是同构的,它们在图论意义上就是彼此同胚的。
总的来说, 一个图G 的剖分 (有时被称为 扩展[1])是指对G中的边做剖分而得到的图。对某条以{u,v}为顶点的边e做剖分会生成一个图,包含新顶点w 和一组边,其中两条新的边{u,w}和{w,v}替代了边e。
例如,边为e,顶点为{u,v }:
可被剖分为两条边,e1 和 e2,连接到一个新顶点 w:
逆向的操作,对顶点w 和与之相连的两条边(e1 ,e2 )做平滑,是指删除连接w 的两条边, 并用一条连接另外两端顶点的新边代替(e1 ,e2 )。需要强调的是,只有度为2的顶点可以被平滑掉。 例如,一个简单的连通图有两条边的图, e1 {u,w }和 e2 {w,v }:
和一个顶点(称为w),顶点可以被平滑掉,生成下面的图:
对图G 和H 而言,判断H 是否与G 的子图同胚 ,是一个NP-完全问题。[2]
重心剖分会剖分图的每一条边。这是一种特殊的剖分,因为它总是产生二分图。这个过程可一直重复下去,继而第n个重心剖分就是对图的第n-1个重心剖分做的重心剖分。另外,这样的剖分图始终是简单图。
显然,对一个图做的剖分保留了图的可平面性。库拉托夫斯基(Kuratowski)定理声明
实际上,一个与 K5 或者 K3,3 同胚的图被称为库拉托夫斯基(Kuratowski)子图。
根据罗伯逊-西摩(Robertson–Seymour)定理的推广,可以确定对于每个整数g,存在一组有限的障碍图集 ,那么当且仅当图H 不包含任何一个 的同胚副本时,H 就可嵌入到亏格为g 的表面上 。例如, 是由库拉托夫斯基(Kuratowski)子图组成。
^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..
^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..
暂无