圖形上有關控制問題之研究以及相關的標號問題之探討;The Study of Varied Domination Problems and Related Labeling Problems in Graphs

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/45889

Title:	圖形上有關控制問題之研究以及相關的標號問題之探討;The Study of Varied Domination Problems and Related Labeling Problems in Graphs
Authors:	廖勝強
Contributors:	數學系
Keywords:	數學類
Date:	2008-07-01
Issue Date:	2010-12-28 15:40:20 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	由於實際上的資源分享問題,我們將考慮一些在圖形上控制問題的變形.原本的圖形上的控制問題是找最少數目的點集合,使得圖上的任一點若不在這個點集合裡,那與它相連接的點裡,至少有一點是落在這個點集合裡.而我們考量的資源分配問題與控制問題相似,我們希望找最少數目的點集合,集合裡的每個點給予完整的資源(用3來衡量),這集合裡的點會供給與它最短距離為一的點部分資源(用2來衡量),供給與它最短距離為二的點少部分資源(用1來衡量),與它最短距離超過二的點就得不到它的資源,而圖上任一點都必須得到完整的資源供給(至少是3).我們已有一些初步的結果,包括證明了這樣的問題就算只考慮二部圖也是NP-complete,給出一些特定圖形上這樣的點集合數目最少的確切值.雖然現在有人提出在樹上,如果給定它的最大鄰居數,就會有個polynomial time的演算法.我們期望能找出更好的演算法,並且解決一些人們關心的特殊圖,如一些有k-規則和k-連通的圖.而透過圖形建構的工具, 如笛卡爾乘績等, 又如何去找到最佳的點集合.此外,我們也對類似的控制問題感興趣, 如「k-局部控制」以及「總體防禦聯盟」等問題. 另外延續之前計劃的工作, 繼續對有關的圖形標號加以研究, 如「L(2,1)標號」以及「圖的整數和數」等問題. 研究期間：9608 ~ 9707
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Mathematics] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	392	View/Open

社群 sharing

Loading...