跳到主要內容

臺灣博碩士論文加值系統

(44.212.99.248) 您好!臺灣時間:2023/01/28 12:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:吳文娟
研究生(外文):Wen-Chuan Wu
論文名稱:完全二部重邊有向圖之小迴圈充填之研究
論文名稱(外文):Packing Complete Bipartite Multidigraphs with Short Circuits
指導教授:李鴻志李鴻志引用關係
指導教授(外文):Hung-Chih Lee
學位類別:碩士
校院名稱:嶺東科技大學
系所名稱:資訊科技應用研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:35
中文關鍵詞:圖形充填圖形分解迴圈充填有向迴圈完全二部重邊有向圖最大4-有向迴圈充填最大6-有向迴圈充填最大8-有向迴圈充填
外文關鍵詞:Graph packinggraph decompositionCycle packingdirected cyclecomplete bipartite multidigraphsmaximum 4-circuit packingmaximum 6-circuit packingmaximum 8-circuit packing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:89
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
圖形充填(含圖形分解)與許多數學結構有密切關係,而且其結果可廣泛地應用在其他領域,例如:編碼理論、多處理器網路、同步光纖網路、DNA篩選、實驗設計、排程問題等,已成為圖形理論中非常重要的一個研究主題。迴圈充填是特殊形式的圖形充填問題,現今這方面的研究仍極為盛行。
一個k-有向迴圈是長度為k的有向迴圈。多重邊有向圖G的一個邊互斥子圖集,若其中每個子圖皆同構於k-有向迴圈,則稱其為G的一個k-有向迴圈充填;若該充填的元素個數為最多,則稱其為最大充填。本論文探討完全二部重邊有向圖的最大4-有向迴圈充填,最大6-有向迴圈充填及最大8-有向迴圈充填問題。對於每個問題,本論文皆得到完整的解答。
Graph packing、including graph decomposition、is an important subject of graph theory since many mathematical structures are linked to it and its results can be applied in coding theory、multicomputer networks、synchronous optical networks (SONET)、DNA library screening、experimental design、scheduling、and other fields. Cycle packing is a special type of graph packing and continues to be a popular topic of research.
A k-circuit is a directed cycle of length k. For a multidigraph G、a k-circuit packing of G is a set of arc-disjoint k-circuits in G. A k-circuit packing of G which has the maximum number of members among all packings is referred as to a maximum k-circuit packing. In this thesis we investigate the problem of finding maximum packings of the complete bipartite multidigraphs with k-circuits for k=4、6 and 8、and give a complete solution to each case.
Contents
Abstract in Chinese……………………………………………………………………… i
Abstract in English……………………………………………………………………… ii
Acknowledge ……………………………………………………………………………. iii
Contents………………………………………………………………………………….. iv
List of Tables……………………………………………………….……………………. v
1. Introduction 1
1.1 Introduction to circuit packings….……………………………………………...1
1.2 Preliminaries………………………..……………………………………………3
1.3 Overview of the thesis………………………..………….………………………4
2. Packing Complete Bipartite Multidigraphs with 4-circuits 5
2.1 4-circuit decompositions………………………………………………………….. 5
2.2 Maximum 4-circuit packings……………………………...………….……...…… 6
3. Packing Complete Bipartite Multidigraphs with 6-circuits 9
3.1 6-circuit decompositions…………………………………………………..……….9
3.2 Maximum 6-circuit packings.……………………………………………..….…10
4. Packing Complete Bipartite Multidigraphs with 8-circuits 16
4.1 8-circuit decompositions………………….………………………………………16
4.2 Small cases………………………………………………………………..………18
4.3 Maximum 8-circuit packings…………………..………………………….………28
Bibliography 34




List of Tables
1.1 Definition of notations…………………….………………………..……………….3
2.1 The minimum leaves of 4-circuit packings of λK*m,n…………….........………….7
3.1 The minimum leaves of 6-circuit packings of λK*m,n……………........………….15
4.1 The minimum leaves of 8-circuit packings of λK*m,n……..…………..………….33
[1] F. E. Bennett and J. Yin 、Packings and coverings of the complete directed multi-
graph with 3- and 4-circuits、Discrete. Math. 162 (1996)、23-29.
[2] E. J. Billington、H.-L. Fu and C. A. Rodger、Packing complete multipartite graphs
with 4-cycles、J. Comb. Des. 9 (2001)、107-127.
[3] E. J. Billington、H.-L. Fu and C. A. Rodger、Packing ¸-fold complete multipartite
graphs with 4-cycles、Graphs Comb. 21 (2005)、169-185.
[4] L. Brown、G. Coker、R. Gardner and J. Kennedy、Packing the complete bipartite
graph with hexagons、Congr. Num. 174 (2005)、97-106.
[5] M. K. Fort、Jr. and G. A. Hedlund 、Minimal coverings of pairs by triples、Paci¯c
J. Math.、8 (1958)、709-719.
[6] H.-L. Fu and M.-H. Huang 、Packing balanced complete multipartite graphs with
hexagons、Ars Combin. 71 (2004)、49-64.
[7] D. G. Ho®man and W. D. Wallis 、Packing complete graphs with squares、Bull.
ICA 1 (1991)、89-92.
[8] J. A. Kennedy 、Maximum packings of Kn with hexagons、Australas. J. Combin.
7 (1993)、101{110 ; Corrigendum: ibid 10 (1994)、293.
[9] J.-J. Lin (in press)、Maximum packings of complete graphs with octagons、Ars
Combin.
[10] A. Rosa and S. Zn¶am 、Packing pentagons into complete graphs: how clumsy can
you get? Discrete Math. 128 (1994)、305-316.
[11] J. SchÄonheim and A. Bialostocki 、Packing and covering the complete graph with
4-cycles、Canad. Math. Bull. 18 (1975)、703-708.
[12] D. Sotteau、Decomposition of Km;n (K¤m;n) into Cycles (Circuits) of Length 2k、J.
Comb. Theory、Ser. B 30 (1981)、75-81.
[13] W.-C. Wu、H.-C. Lee and J.-J. Lin、Packing and covering complete bipartite
multidigraphs with 4-cycles、Ling Tung J. 24 (2008)、223-231.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top