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

NCU Institutional Repository > 理學院 > 數學系 > 研究計畫 > Item 987654321/45889

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/45889

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

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	392	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....