基于贪婪算法的边度量维数问题的研究

发布时间：2022-09-27 17:12

　　求解边度量生成集及边度量维数是图论和组合优化领域的一个重要问题.边度量维数是近些年提出来的研究对象.给定一个连通图G＝（V,E）,顶点w∈V到边e=uv∈E的距离定义为d（w,e）=min{d（u,w）,d（v,w）}.一个顶点子集S称作图G的边度量生成集,如果对于边集E中任意两条不同的边e1,e2 ∈E,在顶点子集S中都存在一个顶点w∈S,使得d（w,e1）≠d（w,e2）.本文通过构作一个合适的势函数,进而给出了关于边度量维数问题的贪婪算法.所得结论:1.构作了一个解决一般图上边度量维数问题的贪婪算法.2.对构作的贪婪算法,给出了近似比（1+lnn）+ln（log2n）,其中n是图G中顶点的个数.3.对圈和树给出了解决赋权的边度量维数问题的算法. 

【文章页数】：35 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
引言
第一章 预备知识
    1.1 相关概念和性质
    1.2 贪婪算法和次模理论
    1.3 赋权的边度量维数
第二章 图的边度量维数问题的一种贪婪算法
    2.1 势函数的构作
    2.2 贪婪算法
第三章 算法的理论分析
    3.1 相关引理
    3.2 近似比分析
第四章 赋权的边度量维数问题
    4.1 圈的赋权边度量维数
    4.2 树的赋权边度量维数
结论
参考文献
致谢
攻读学位期间取得得的科研成果清单



本文编号：3681274