重邊圖之分解圖形分解是圖論中受到很多研究者注意得研究領域。圖形分解在討論把一個圖的邊分解成幾個具有某種特性的圖。在文獻上,多數論文都在研究單邊圖(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