小圈二重覆盖三角剖分图(英文)  

Small Circuit Double Covers of Near Triangulations

作　　者：刘同印[1] 

机构地区：[1]北方交通大学理学院

出　　处：《北方交通大学学报》1999年第2期65-67,共3页Journal of Northern Jiaotong University

摘　　要：近三角剖分图是一连通平面图，其内面均为三角形，而其外面可能不是．图Ｇ的一个二重覆盖（ＣＤＣ）指它的一个圈族Ｃ，使得Ｇ的每条边恰属于Ｃ的两个元素．令Ｇ为一个具有ｎ个节点的２－连通平面图，Ｃ为Ｇ的一个ＣＤＣ．若｜Ｃ｜≤ｎ－１，则称Ｃ为Ｇ的一个小圈二重覆盖（ＳＣＤＣ）．本文证明每个近三角剖分图均存在一个ＳＣＤＣ．A near triangulation is such a connected planar graph whose inner faces are all triangles but the outer face may be not. A circuit double cover (CDC) of a graph G is a collection C of circuits such that each edge of G belongs to two members of C exactly. Let G=(V,E) be a 2-connected planar graph of order n and C be a CDC of G . If |C|≤n-1, C is said to be a small circuit double cover (SCDC) of G . In this paper, we prove that every near triangulation admits an SCDC.

关 键 词：圈二重覆盖 小圈二重覆盖 三角剖分 连通图 

分 类 号：O157.5[理学—数学]