特殊图上的（带权值的）2-分辨集问题的研究

发布时间：2023-12-03 19:39

　　设G=(V,E,C)为非负加权简单图,S(?)V,若对任意的u,v∈V,存在x,y∈S,满足-d(x,u)-(x,y)≠d(y,u)-d(y,v),则称5为G的2-分辨集。(带权值的)2-分辨集问题就是求解图权值最小的2-分辨集。本文先对树状图上(带权值的)2-分辨集进行探究,提出W-2-分辨集的概念,证明对于树状图G=∪ni=1 Gi=∪ni=1(Vi,Ei,Ci),Gi为G的块,若W为G的割点集,Wi=Vi≌∩W,Si为Gi,的权值最小的Wi-2-分辨集,则∪ni=1 Si\W为G的最小2-分辨集。进一步的,本文对块图、仙人掌图上的(带权值)的2-分辨集问题给出了线性时间算法。对于k-边树上(带权值)的2-分辨集问题,定义K块和“路”的概念,并证明了对于k-边树G,若G有p个K块,则G上(带权值)的2-分辨集问题有O(n12k-8p)多项式时间算法。

【文章页数】：36 页

【学位级别】：硕士

【文章目录】：
中文摘要
abstract
1 绪论
    1.1 图的基本概念
2 2-分辨集问题
    2.1 分辨集和2-分辨集问题简介
    2.2 2-分辨集问题研究现状
    2.3 本文成果
3 树状图上(带权值)的2-分辨集问题
    3.1 基本性质
    3.2 块图上(带权值)的2-分辨集问题
    3.3 仙人掌图上的2-分辨集问题
    3.4 仙人掌图上(带权值的)2-分辨集问题
4 k边-树上2-分辨集问题的讨论
参考文献
致谢



本文编号：3870249