求解邊度量生成集及邊度量維數(shù)是圖論和組合優(yōu)化領(lǐng)域的一個(gè)重要問題.邊度量維數(shù)是近些年提出來的研究對(duì)象.給定一個(gè)連通圖G＝（V,E）,頂點(diǎn)w∈V到邊e=uv∈E的距離定義為d（w,e）=min{d（u,w）,d（v,w）}.一個(gè)頂點(diǎn)子集S稱作圖G的邊度量生成集,如果對(duì)于邊集E中任意兩條不同的邊e1,e2 ∈E,在頂點(diǎn)子集S中都存在一個(gè)頂點(diǎn)w∈S,使得d（w,e1）≠d（w,e2）.本文通過構(gòu)作一個(gè)合適的勢(shì)函數(shù),進(jìn)而給出了關(guān)于邊度量維數(shù)問題的貪婪算法.所得結(jié)論:1.構(gòu)作了一個(gè)解決一般圖上邊度量維數(shù)問題的貪婪算法.2.對(duì)構(gòu)作的貪婪算法,給出了近似比（1+lnn）+ln（log2n）,其中n是圖G中頂點(diǎn)的個(gè)數(shù).3.對(duì)圈和樹給出了解決賦權(quán)的邊度量維數(shù)問題的算法. 

【文章頁數(shù)】：35 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
中文摘要
英文摘要
引言
第一章 預(yù)備知識(shí)
    1.1 相關(guān)概念和性質(zhì)
    1.2 貪婪算法和次模理論
    1.3 賦權(quán)的邊度量維數(shù)
第二章 圖的邊度量維數(shù)問題的一種貪婪算法
    2.1 勢(shì)函數(shù)的構(gòu)作
    2.2 貪婪算法
第三章 算法的理論分析
    3.1 相關(guān)引理
    3.2 近似比分析
第四章 賦權(quán)的邊度量維數(shù)問題
    4.1 圈的賦權(quán)邊度量維數(shù)
    4.2 樹的賦權(quán)邊度量維數(shù)
結(jié)論
參考文獻(xiàn)
致謝
攻讀學(xué)位期間取得得的科研成果清單



本文編號(hào)：3681274