博碩士論文 84241002 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:5 、訪客IP:3.233.217.242
姓名 李鴻志(Hung-Chih Lee)  查詢紙本館藏   畢業系所 數學系
論文名稱 圖之均勻分解與有向圖之因子分解
(Balanced Decompositions of Graphs and Factorizations of Digraphs)
相關論文
★ 加權圖之和、中位點及位移★ 迴圈之冪圖的星林分解數
★ 圖形的線性蔭度及星形蔭度★ On n-good graphs
★ A Note On Degree-Continuous Graphs★ Status Sequences and Branch-Weight Sequences of Trees
★ n-realizable Quadruple★ 圖形的路徑分解,迴路分解和星形分解
★ 星林圖的二分解與三分解★ 2-decomposable, 3-decomposable multipaths and t-decomposable spiders
★ 圖形分解與反魔圖★ The antimagic graph with a generalization
★ 圖的程度序列和狀態★ The 3-split of multipaths and multicycles with multiplicity 2
★ 圖形之分割與反魔標號
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 由於與其他數學結構的緊密連結,及其結果可廣泛地應用在其他領域,
圖形分解(graph decomposition)已成為圖形理論中
非常重要的一個主題。
均勻分解(balanced decomposition)及因子分解(factorization)
是兩種特定形式的分解問題,
其與組合設計(combinatorial design)有著密切的關聯性。
多重邊完全圖(complete multigraph)的均勻分解與因子分解,
分別對應於均勻不完全區塊設計(balanced imcomplete block design, BIBD)
與可分解設計(resolvable design)。
如今,這兩方面的研究仍極為盛行。
圖形分解有許多種類型,諸如完全圖分解(clique decomposition)、
星形分解(star decomposition)、路徑分解(path decomposition)、
迴路分解(cycle decomposition)以及
完全二部圖分解(complete bipartite decomposition)等等。
本論文主要在探討無向圖(undirected graph)之
均勻星形分解(balanced star decomposition)與
均勻路徑分解(balanced path decomposition),
以及有向圖(digraph)之
有向星形因子分解(directed star factorization)與
有向路徑因子分解(directed path factorization)等問題。
本篇論文分成六章。首章我們介紹一些基本定義及所使用的符號。
在第二章中,我們探討均勻星形分解。
我們得到規則多重邊圖(regular multiple graph)
以及多重邊完全二部圖(complete bipartite multigraph)
(當兩分部點數不同時,其為非規則圖)分解成均勻星形的充要條件。
在第三章中,我們探討路徑分解問題。
首先我們得到多重邊完全二部圖分解成均勻路徑的充要條件;
其次我們給予完全三部圖(complete tripartite graph)
(分部之點數為奇數)分解成路徑之充要條件。
在第四章中,我們探討皇冠圖(crown)的
分解不變量(decomposition invariants),
其中包含了路徑數(path number)、線性蔭度(linear arboricity)
以及星形蔭度(star arboricity)。
在第五章中,首先我們探討對稱皇冠圖(symmetric crown)
因子分解成有向星形及有向路徑之問題,並得到其充要條件。
其次我們探討對稱完全多部有向圖(symmetric complete multipartite digraph)
的星形因子分解問題,並給予一些充份條件。
在第六章中,我們
探討對稱完全二部有向圖(symmetric complete bipartite digraph)
的雙向星形分解(distar decomposition)問題,
並得到一些充份條件。
摘要(英) Graph decomposition is an important subject of graph theory
since many mathematical structures are linked to it and
its result can be widely applied in other fields.
Balanced decomposition and factorization are
special types of graph decomposition,
and they have close connections to combinatorial designs.
Balanced decompositions of complete multigraphs and
factorizations of complete multigraphs correspond to
blanced imcomplete block designs (BIBD) and
resolvable designs, respectively.
Nowadays, they continue to be popular topics of research.
There are various decomposition problems such as
clique decomposition, star decomposition,
path decomposition, cycle decomposition,
complete bipartite decomposition, and so on.
In theis thesis, the problems of balanced star decomposition and
balanced path decomposition of some graphs,
and that of directed star factorization and
directed path factorization of some digraphs are investigated.
There are six chapters in this thesis.
In Chapter 1, some basic definitions and notation are introduced.
In Chapter 2,
the balanced star decompositions of graphs are investigated.
We first give a criterion for the balanced star decompositions of
regular multiple graphs.
We then give a necessary and sufficient condition
for the existence of the balanced star decompositions of
complete bipartite multigraphs which are not regular
if the partite sets have different size.
In Chapter 3, the path decomposition of graphs are studied.
We first establish a necessary and sufficient condition
for the balanced path decomposition of
complete bipartite multigraph.
We then give a criterion for the path decomposition of
complete tripartite graph.
In Chapter 4,
we find some decomposition invariants of crown, which include
the path number, linear arboricity and star arboricity.
In Chapter 5,
we first consider the problems of directed star factorizations and
directed path factorizations of the symmetric crown,
the necessary and sufficient conditions are given.
We then study directed star factorization of the symmetric
complete mutipartite digraph and give some sufficient conditions.
In Chapter 6,
we consider the problem of decomposing
the symmetric complete bipartite digraph into distars,
some sufficient conditions are given.
關鍵字(中) ★ 星形
★ 因子分解
★ 均勻分解
★ 有向圖
★ 圖形
★ 路徑
關鍵字(英) ★ graph
★ digraph
★ balanced decomposition
★ factorization
★ star
★ path
論文目次 論文提要
誌謝
Abstract
Contents
List of Figures
1 Introduction
1.1 Introduction to decompositions and factorizations of graphs
1.2 Preliminaries
1.3 Overview of the thesis
2 Balanced Star Decompositions
2.1 Introduction
2.2 Balanced star decompositions of regular multiple graphs
2.3 Balanced star decompositions of ?- fold complete bipartite graphs
3 Path Decompositions of Bipartite Graphs and Tripartite Graphs
3.1 Introduction
3.2 Balanced path decompositions of ?-fold complete bipartite graphs
3.3 Path decompositions of complete tripartite graphs
4 Decomposition Invariants of Crowns
4.1 Introduction
4.2 Path numbers and linear arboricities of
4.3 Star arboricities of ??

5 Directed Star-Factorizations and Directed Path-Factorizations
5.1 Introduction
5.2 Directed star-factorizations of symmetric crowns
5.3 Directed path-factorizations of symmetric crowns
5.4 Directed star-factorizations of the ?- fold symmetric complete multipartite digraphs
6 Distar Decompositions of the Complete Bipartite Digraphs
6.1 Introduction
6.2 Ncecessary conditions
6.3 Sufficient conditions
Bibliography
參考文獻 J. Akiyama, G. Exoo and F. Harary,
Covering and packing in graphs III: Cyclic and acyclic invariants,
Math. Slovaca 30 (1980), 405--417.
J. Akiyama, G. Exoo and F. Harary,
Covering and packing in graphs IV: Linear arboricity,
Networks 11 (1981), 69--72.
J. Akiyama and T. Hamada,
The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests,
Discrete Math. 26 (1979), 203--208.
J. Akiyama and M. Kano,
Path factors of a graph, in: Graphs and Applications,
Proceedings of the 1st Colorado Symposium on Graph Theory, 1982, 1--21.
I. Algor and N. Alon,
The star arboricity of graphs,
Discrete Math. 75 (1989), 11--22.
Y. Aoki,
The star-arboricity of the complete regular multipartite graphs,
Discrete Math. 81 (1990), 115--122.
L. W. Beineke,
Graph decompositions,
Congr. Num. 115 (1996), 213--226.
J. C. Bermond and D. Sotteau,
Graph decompositions and G-designs,
Fifth British Combinatorial Conf., Aberdeen
Congr. Num. XV (1975), 53--72.
J. C. Bermond K. Heinrich and M.-L. Yu,
Existence of resolvable path designs
Europ. J. Combinatorics 11 (1990), 205--211.
J. A. Bondy and U. S. R. Murty,
Graph Theory with Applications.
North Holland, New York (1976), 101.
J. Bos 'ak,
Decompositions of Graphs.
Kluwer Academic Publishers, Dordrecht. The Netherlands, 1990.
D. De Caen and D. G. Hoffman,
Impossibility of decomposing the complete graph on n points into n-1
isomorphic complete bipartite graphs,
SIAM J. Discrete. Math. 2 (1989), 48--50.
P.V. Caetano and K. Heinrich,
A note on distar factorizations,
Ars Combin. 30 (1990), 27--32.
N.J. Cavenagh,
Decompositions of complete tripartite graphs into $k$-cycles,
Australasian J. Combin. 18 (1998), 193--200.
G. Chartrand and L. Lesniak,
Graphs and Digraphs (2nd ed.),
Wadsworth, (1986), 85.
F. R. K. Chung and R. L. Graham,
Recent advances in graph decompositions in combinatorics,
Proceeding of 8th British Combinatorial Conference (University College, Swansea, 1981), edited by H.N.V. Temperley,
London Math. Soc. Lecuture Notes 1120, Combridge University Press (1981), 103--124.
C. J. Colbourn, D. G. Hoffman, C. A. Rodger,
Directed star decompositions of the complete directed graph,
J. Graph Theory 16 (1992), 517--528.
C. J. Colbourn, D. G. Hoffman, C. A. Rodger,
Directed star decompositions of directed multigraphs,
Discrete Math. 97 (1991), 139--148.
A. Donald,
An upper bound for the path number of a graph,
J. Graph Theory 4 (1980), 189--201.
B. Du,
$K_{1,p^2}$-factorization of complete bipartite graphs,
Discrete Math. 187 (1998), 273--279.
Y. Egawa, M. Urabe, T. Fukuda and S. Nagoya,
A decomposition of complete bipartite graphs into edge-disjoint subgraphs with star components,
Discrete Math. 58 (1986), 93--95.
S. El-Zanati and C. Vanden,
Cycle factorizations of cycle products,
Discrete Math. 189 (1998), 267--275.
H. Enomoto and Y. Usami,
The star arboricity of cComplete bipartite graphs,
Graph Theory, Combinatorics, and Applications 1 (1988), 389--396.
H. Enomoto, T. Miyamoto and K. Ushio,
$C_k$-factorization of complete bipartite graphs,
J. Graphs Combin. 4 (1988), 111--113.
bibitem{hana}
H. Hanani,
Balanced incomplete block designs,
{ it Discrete Math.}
{ bf 4} (1975), 255--369.
bibitem{hary}
F. Harary and A.J. Schwenk,
Evolution of the path number of a graph:
Covering and Packing in Graphs, uppercase expandafter{ romannumeral 2},
{ it Graph Theory and Computing},
edited by R.C. Read,
Acad. Press, NY, (1972), 39--45.
J. D. Horton,
Resolvable path designs,
J. Combin. Theory, Ser. A 39 (1985), 117--131.
C. Huang and A. Rosa,
On the existence of balanced bipartite designs,
Utilitas Math. 4 (1973), 55--75.
C. Huang,
On the existence of balanced bipartite designs II,
Discrete Math. 9 (1974), 147--159.
C. Huang,
Resolvable balanced bipartite designs,
Discrete Math. 14 (1976), 319--335.
S. H. Y. Hung and N. S. Mendelsohn,
Handcuffied designs,
Deiscrete Math. 18 (1977), 23--33.
B. W. Jackson,
Some cycle decompositions of complete graphs,
Journal of Combinatorics, Information & System Sciences 13 (1988), 20--32.
L. O. James, R. G. Stanton and D. D. Cowan,
Some results on tree numbers,
Proceedings of the Second Louisiana Conference on Combinatorics,
Graph Theory and Computing, Baton Rouge, (1971), 317--330.
A. Kurek,
Arboricity and star arboricity of graphs,
Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice,1990),
Annal Discrete Math. 51 (1992), 171-173.
C. Lin and J.-J. Lin,
Cycle decompositions of crowns,
Discrete Math., to appear.
C. Lin, J.-J Lin, and H.-C. Lee,
Some decomposition invariants of crowns,
Submitted.
C. Lin, J.-J. Lin and T.-W. Shyu,
Complete bipartite decomposition of crowns,
with applications to complete directed graphs,
Lecuture Notes in Computer Science 1120 (1996), 58--66.
C. Lin, J.-J. Lin and T.-W. Shyu,
Isomorphic star decomposition of multicrowns and the power of cycles,
ARS Combinatoria, 53 (1999), 249-256.
C. Lin and T.-W. Shyu,
A necessary and sufficient condition for the star decomposition of complete graphs,
J. Graph Theory 23 (1996), 361--364.
J.-J. Lin,
Multiple Star Decompositions of Complete Multigraphs and Some Decompositions of Crowns,
Ph.D. Thesis, Department of Mathematics, National Central University, Taiwan (1999).
C. C. Lindner and C. A. Rodger,
Decomposition into cycles II: Cycle systems, in
Contemporary Design Theory, edited by J.H. Dinitz, D.R. Stinson.
John Wiley and Sons, Inc. (1992), 325--369.
L.Lov 'asz,
On covering of graphs, in it Theory of Graphs
(Proceedings of the Colloquium held at Tihany, Hungary, September, 1966),
edited by P. Erd "os and G. Katona, Academic, New York (1968), 231--236.
N. Martin,
Complete bipartite factorizations by complete bipartite graphs,
Discrete Math. 167/168 (1997), 461--480.
N. Martin,
Balanced bipartite graphs may be completely star-factored,
J. Combin. Des. 5 (1997), 407--415.
A. Muthusamy and P. Paulraja,
Path factorizations of complete multipartite graphs,
Discrete Math. 195 (1999), 181--201.
C. St. J. A. Nash-Williams,
Decomposition of finite graphs into forests,
J. London Math. Soc. 39 (1964), 12.
D. Pritikin,
Applying a proof of Tverberg to complete
bipartite decompositions of dgraphs and multigraphs,
J. Graph Theory 10 (1986), 197--201.
H.J. Ryser,
Combinatorial properties of matrices of zeros and ones,
Canad. J. Math. 9 (1957), 371--377.
H. J. Ryser,
Combinatorial Mathematics.
Carus Math. Monograph 14 (1963), 63.
I. Satake,
Linear Algebra.
Marcel Dekker, Inc, New York (1975), 91.
T.-W. Shyu,
The Decomposition of Complete Graphs, Complete Bipartite Graphs and Crowns,
Ph.D. Thesis, Department of Mathematics, National Central University, Taiwan (1997).
D. Sotteau,
Decomposition of $K_{m,n}(K_{m,n}^* )$ into cycles (circuits) of length 2k,
J. Combin. Theory, Ser. B 30 (1981), 75--81.
R.G. Stanton, D.D. Cowan and L.O. James,
Some results on path numbers,
Proceedings of the first Louisiana Conference on Combinatorics,
Graph Theory and Computing}, Baton Rouge, (1970), 112--135.
R. G. Stanton, D. D. Cowan and L. O. James,
Some results on tree numbers,
Proceedings of the Second Louisiana Conference on Combinatorics,
Graph Theory and Computing, Baton Rouge, (1971), 317--330.
M. Tarsi,
Decomposition of complete multigraphs into stars,
Discrete Math. 26 (1979), 273--278.
M. Tarsi,
On the decomposition of a graph into stars,
Discrete Math. 36 (1981), 299--304.
M. Tarsi,
Decomposition of complete multigraph into simple paths: nonbalanced handcuffied designs,
J. Combin. Theory, Ser. A 34 (1983), 60--70.
S. Tazawa,
Decomposition of a complete multipartite graph into isomorphic claws,
SIAM J. Algebraic Discrete Methods 6 (1985), 413--417.
M. Truszczynski,
Note on the decomposition of $ l K_{m,n}( l K^*_{m,n})$ into paths,
Discrete Math. 55 (1985), 89--96.
M. Truszczynski,
Decomposing graphs into forests of stars,
Congr. Numer. 54 (1986), 73--86.
H. Tverberg,
On the decomposition of $K_n$ into complete bipartite graphs,
J. Graph Theory 6 (1982), 493--494.
K. Ushio, S. Tazawa and S. Yamamoto,
On claw decomposition of complete multipartite graphs,
Hiroshima Math. J. 8 (1978), 207--210.
K. Ushio,
On balanced claw designs of complete multipartite graphs,
Discrete Math. 38 (1982), 117--119.
K. Ushio,
G-designs and related designs,
Discrete Math. 116 (1993), 299--311.
K. Ushio,
Star-factorization of symmetric complete bipartite digraphs,
Discrete Math. 167/168 (1997), 593--596.
K. Ushio,
$ hat{S_k}$-factorization of symmetric complete tripartite digraphs,
Discrete Math. 197/198 (1999), 791--799.
K. Ushio,
Cycle-factorization of symmetric complete tripartite digraphs,
Discrete Math. 199 (1999), 273--278.
K. Ushio,
$ bar{S_k}$-factorization of symmetric complete tripartite digraphs,
Discrete Math. 211 (2000), 281--286.
H. Wang,
On $K_{1,k}$-factorizations of a complete bipartite graph,
Discrete Math. 126 (1994), 359--364.
S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio, and N. Hamada,
On claw-decomposition of complete graphs and complete bigraphs,
Hiroshima Math. J. 5 (1975), 33--42.
M.-L. Yu,
Resolvable tree designs,
J. Combin. Theory, Ser. A 61 (1992), 302--308.
M.-L. Yu,
On tree factorizations of $K_n$,
J. Graph Theory 17 (1993), 713--725.
M.-L. Yu,
On path factorizations of complete multipartite graphs,
Discrete Math. 122 (1993), 325--333.
指導教授 林強(Chiang Lin) 審核日期 2000-6-27
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明