發(fā)布時間：2023-12-03 19:39

　　設(shè)G=(V,E,C)為非負(fù)加權(quán)簡單圖,S(?)V,若對任意的u,v∈V,存在x,y∈S,滿足-d(x,u)-(x,y)≠d(y,u)-d(y,v),則稱5為G的2-分辨集。(帶權(quán)值的)2-分辨集問題就是求解圖權(quán)值最小的2-分辨集。本文先對樹狀圖上(帶權(quán)值的)2-分辨集進(jìn)行探究,提出W-2-分辨集的概念,證明對于樹狀圖G=∪ni=1 Gi=∪ni=1(Vi,Ei,Ci),Gi為G的塊,若W為G的割點(diǎn)集,Wi=Vi≌∩W,Si為Gi,的權(quán)值最小的Wi-2-分辨集,則∪ni=1 Si\W為G的最小2-分辨集。進(jìn)一步的,本文對塊圖、仙人掌圖上的(帶權(quán)值)的2-分辨集問題給出了線性時間算法。對于k-邊樹上(帶權(quán)值)的2-分辨集問題,定義K塊和“路”的概念,并證明了對于k-邊樹G,若G有p個K塊,則G上(帶權(quán)值)的2-分辨集問題有O(n12k-8p)多項式時間算法。

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

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

【文章目錄】：
中文摘要
abstract
1 緒論
    1.1 圖的基本概念
2 2-分辨集問題
    2.1 分辨集和2-分辨集問題簡介
    2.2 2-分辨集問題研究現(xiàn)狀
    2.3 本文成果
3 樹狀圖上(帶權(quán)值)的2-分辨集問題
    3.1 基本性質(zhì)
    3.2 塊圖上(帶權(quán)值)的2-分辨集問題
    3.3 仙人掌圖上的2-分辨集問題
    3.4 仙人掌圖上(帶權(quán)值的)2-分辨集問題
4 k邊-樹上2-分辨集問題的討論
參考文獻(xiàn)
致謝



本文編號：3870249