图的一种覆盖和特征数
kind of cover of a graph and graph characteristic number
我们称图G的一个子图R是G的一个CP-覆盖，如果V(R)=V(G)并且R中所有点的度都不大于2，即R是G中两两不相交的圈，路和孤立点的并。定义了反映一个 CP-覆盖中路和孤立点 数目的特征数。显然一个图可以有很多CP-覆盖，其中含路的数目和孤立点的数目最少，也即特征数最小的的我们称之为图的最大CP-覆盖，其特征数被称为图G的特征数。本文给出了求一个图的特征数和相应最大 CP-覆盖的一个多项式时间算法。 一个不含路和孤立点的CP-覆盖称为C-覆盖，显然C-覆盖是最大CP-覆盖，其相应的特征数是零。一个H 图的一个H 圈是它的一个C-覆盖，其特征数是零，即H图的一个必要条件是它有一个C-覆盖，即其特征数是零。本文给出的算法使得此条件是多项式时间可检验的。
subgraph S of a graph G is called a CP-cover of G,if V(G)=V(S) and the degree of a vertex in S does not exceed 2.that is,S is a union of circuits,paths and isolated vertices in G,which have no common vertex.We definition a characteristic number for a CP-cover,which reflect the number of the paths and isolated vertices in a CP-cover of G.The CP-cover of G are called maximum if the characteristic number of it is minimum,and the characteristic number is called characteristic number of G.We give a polynomial time algorism for finding a maximum CP-cover of a graph G in this paper. We call a CP-cover a C-cover ,if it\\\
谢应泰
数学
H图H圈交替链P-覆盖-覆盖P-链
P-cover-coverP-chainH graphH circuit
谢应泰.图的一种覆盖和特征数[EB/OL].(2009-02-10)[2025-08-10].http://www.paper.edu.cn/releasepaper/content/200902-312.点此复制
评论