论文部分内容阅读
考虑一个顶点赋权图，定义图中每个顶点子集的权重为其包含的顶点总权重，同时，如果存在某个顶点子集，满足图中每条边均至少有一个端点属于该顶点子集，则称其为顶点覆盖集。顶点覆盖问题是指在给定的图G中寻找一个权重最小的顶点覆盖集。该问题作为图论经典问题，受到了研究者的广泛关注。本文主要研究内容之一是顶点覆盖问题的两个推广问题——部分顶点覆盖问题与奖励收集顶点覆盖问题。 如果要求顶点子集只需覆盖图中至少k条边，则顶点覆盖问题就转化为部分顶点覆盖问题，显然有当k取到图的边数时，部分顶点覆盖问题将退化为顶点覆盖问题。类似地，如果给每条边赋予惩罚费用，对于图中的顶点子集，定义一种特殊的权重，为其包含的顶点总权重加上未被其覆盖的边的总费用，目标为寻找一个权重最小的顶点子集，则称为奖励收集顶点覆盖问题，显然有惩罚费用均远大于顶点权值时，奖励收集顶点覆盖问题将退化为顶点覆盖问题。 本文采用迭代松弛方法依次设计了部分顶点覆盖问题的一个近似度为2+Q/OPT的近似算法，其中Q表示有限的最大的顶点权值，OPT表示该问题的最优解的值，一个近似度为2的近似算法，以及奖励收集顶点问题的一个2-近似算法。 图不变量，指图（或图的一部分）到实数集的一个映射，并且其在同构图中取值相同。其中，基于顶点间距离的一系列图不变量在理论化学领域得到了广泛的研究和应用。本文着重研究了度阻尼距离，其由Gutman等在2012年首次提出，其定义为DR(G)=∑{u，v}(C)V(G)[dG(u)+dG(v)]RG(u，v)，其中dG（u）表示顶点u的度，RG（u，v）表示顶点u，v之间的阻尼距离。我们研究并刻画了具有最大度阻尼距离的单圈图和双圈图，以及具有最小度阻尼距离的仙人掌图。