重邊圖之分解; Decompositions of Multigraphs

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

Title:	重邊圖之分解;Decompositions of Multigraphs
Authors:	林強
Contributors:	數學系
Keywords:	數學類
Date:	2007-07-01
Issue Date:	2010-12-21 17:26:00 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	重邊圖之分解圖形分解是圖論中受到很多研究者注意得研究領域。圖形分解在討論把一個圖的邊分解成幾個具有某種特性的圖。在文獻上，多數論文都在研究單邊圖(simple graph)的分解。本計劃的目的在探討多邊圖(multigraph)分解的幾個問題。定義：若，GH皆為圖(graph)，且G的邊可分解成幾個H，則稱G有H-分解。符號：1. ：個點的完全圖。 nKn 2. ：個邊的星圖(star)。 mSm 3. 若為一圖，則GGλ為把的每一邊都用Gλ個邊來取代的圖。在1979, M. Tarsi [T]研究完全多邊圖之同構星圖分解，證得：定理A nKλ has an -decomposition if and only if mS )1(\|2.nnmλ and .....2nm. 1=λ 1..nm even λ λ11)1(+..nm odd 3.λ. 在1996, C. Lin與T.-W. Shyu [LS]考慮把完全圖分解成數個不要求一定要同構的星圖而得到：定理B nK can be decomposed into stars,…,, where if and only if 1mSlmSlmm..L1 ........=Σ=21nmii l . . k i k i m n i 1 1 ( ) ΣΣ= . 1,...,2,1.=nk =i 在2005, H.-J. Lee等人 [L]推廣定理B成：定理C nKλ can be decomposed into l multistars, each of which has edges(, respectively if and only if lmm,,1L) 1 l m . L . m ........=Σ=21nmliiλ ΣΣ==..kikiiinm11)(λ .1,...,2,1.=nk 在定理C中，邊數相同的多邊星並沒要求為同構。Lee等人[L]也探討把重邊完全圖分解成同構的重邊星圖，而得：定理D Let be a multistar contained in such that has m edges where S nK2S (1) and )1(\|.nnm (2) 2nm. or or . 1.=nmnm= Then has an nK2.Sdecomposition. 本計劃將探討下列兩個問題： 1. 定理A是把nKλ分解成同構的星圖，定理B是把分解成不需要同構的星圖。而自然地，把nKnKλ分解成不需要同構的星圖是個值得研究的問題，我們將從2=λ著手。 2. 在[L]中，有與定理D相關的猜測如下： Let be a multistar contained in such that has edges whereSnK2Sm)1(\|.nnm, . Then has an decomposition. nm.nK2.S 我們將探討此猜測。研究期間：9508 ~ 9607
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Mathematics] Research Project

Files in This Item:

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

社群 sharing

Loading...