跳到主要內容

臺灣博碩士論文加值系統

(3.237.38.244) 您好!臺灣時間:2021/07/24 17:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:胡世偉
研究生(外文):Shih-Wei Hu
論文名稱:無向圖的零和流與流數性質之研究
論文名稱(外文):On Zero-Sum Flows and Flow Numbers of Undirected Graphs
指導教授:王道明
指導教授(外文):Tao-Ming Wang
口試委員:王道明陳伯亮黃國卿
口試委員(外文):Tao-Ming WangBor-Liang ChenKuo-Ching Huang
口試日期:2012-06-15
學位類別:碩士
校院名稱:東海大學
系所名稱:數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2013
畢業學年度:100
語文別:英文
論文頁數:61
中文關鍵詞:零和流零和流數常數流常數群流常規圖尤拉圖扇圖輪子圖
外文關鍵詞:zero-sum flowzero-sum flow numberconstant-sum flowconstant-sum group flowregular grapheulerian graphfan graphwheel graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:316
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
網路理論是現代通訊和網路系統的基礎,
其中有許多不同的分析方法去研究和傳輸資訊相關的各種問題。
這篇論文是專注在於網路流的問題,
網路流的問題不僅僅只是通訊,
還包括標籤、著色、週期涵蓋以及圖形理論的各種主題分解。

本論文涉及經典的網路流量問題,每個頂點都滿足基爾霍夫流量定律,
包含有向圖內的無處零流以及更普遍的雙向圖內無處零流,
更確切來說,我們處理與零和流動問題,
作為一個雙向導向無處零流量的特殊情況,
和他們的相關的無向圖最小流量數字。

第一章,簡要介紹無處零流的背景和近期理論發展和著名的猜想。
第二章,專門研究流動數字圖表,像是定期圖表、迷圖、輪圖。
第三章,利用第一章的零合流的觀念延伸出常數流。
第四章,為第二、三章代數進一步延伸阿貝爾群流的觀念。
第五章,歸納出來的公開問題。
Network theory is the foundation of modern communication and
internet systems, in which there are many different analytic ways to
study various kinds of problems related to the data transmission.
This thesis is dedicated to certain network flow problem. The
network flow problem is closely related to not just communications,
but also to labeling, coloring, cycle covers, and factorizations
among various topics in graph theory.

This thesis concerns classic network flow problems including the
nowhere-zero flow on directed graphs and more generally the
nowhere-zero flow on bi-directed graphs, for which the Kirchhoff
current law type of flow condition is satisfied along each vertex.
More precisely, we deal with the zero-sum flow problems, as a
special case of the bi-directed nowhere-zero flows, and their
associated minimum flow numbers over undirected graphs.

To begin with, Chapter one gives a brief introduction about the
background of nowhere-zero flows, also the recent theoretical
development and the well-known conjectures. Chapter two is a study
of flow numbers on special classes of graphs, such as regular
graphs, fans graphs, and wheels graphs. On the study of zero-sum
flow in Chapter two, the concept of constant-sum is used. Thus we
define constant-sum flow and study them in Chapter three. Chapter
four is the outcome of further algebraic extension of Chapter two
and Chapter three by extending the integer flows to Abelian group
flows. We conclude with some open problems in the last Chapter five.

1 Nowhere-Zero Flows 1
1.1 Network Flows . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Nowhere-Zero Flows on Directed Graph . . . . . . . . . . . . . 2
1.3 Nowhere-Zero Flows on Bidirected Graphs . . . . . . . . . . . 5

2 Zero-Sum Flows and Zero-Sum Flow Numbers 9
2.1 Survey of Previous Results . . . . . . . . . . . . . . . . . . . . 9
2.2 Zero-Sum Flow Numbers for General Graphs . . . . . . . . . . 12
2.3 Zero-Sum Flow Numbers for Regular Graphs . . . . . . . . . . 14
2.3.1 Even Regular Graphs . . . . . . . . . . . . . . . . . . . 14
2.3.2 2-Edge-Connected Odd Regular Graphs . . . . . . . . . 16
2.4 More Examples of Flow Numbers . . . . . . . . . . . . . . . . 19
2.4.1 Cartesian Product of Regular Graphs With Paths and
Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Fan Graphs and Wheel Graphs . . . . . . . . . . . . . 23
2.4.3 Two Infinite Families of Examples of Zero-Sum Flow
Numbers 5 and 6 . . . . . . . . . . . . . . . . . . . . . 29

3 Constant-Sum Flows 33
3.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Constant-Sum Flows of Regular Graphs . . . . . . . . . . . . 34
3.2.1 Odd Regular Graphs . . . . . . . . . . . . . . . . . . . 34
3.2.2 Even Regular Graphs . . . . . . . . . . . . . . . . . . . 35
3.3 Constant-Sum Flows of Fan Graphs and Wheel Graphs . . . . 37
3.3.1 Fan Graphs . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Wheel Graphs . . . . . . . . . . . . . . . . . . . . . . . 40

4 Constant-Sum Group Flows 43
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Basic Properties and Mini-Survey . . . . . . . . . . . . . . . . 44
4.3 4r-Regular Graphs with Constant-Sum Z4-Flows . . . . . . . . 47

5 Conclusion and Further Studies 48
5.1 Summary of Results . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 49
[1] S. Akbari, N. Ghareghani, G. B. Khosrovshahi, S. Zare, A note on
zero-sum 5-flows in regular graphs, the Electronic Journal of Combinatorics
19(2) (2012), # P7.

[2] S. Akbari, G.B. Khosrovshahi and A. Mofidi, Zero-Sum Flows in
Designs, Journal of Combinatorial Designs 19 (2011), 355-364.

[3] S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian,
Zero-Sum Flows in Regular Graphs, Graphs and Combinatorics 26
(2010), 603-615.

[4] S. Akbari, G.B. Khosrovshahi, N. Ghareghani and A. Mahmoody, On
Zero-Sum 6-Flows of Graphs, linear Algebra and its Applications
430 (2009), 3047-3052.

[5] S. Akbari, G.B. Khosrovshahi, N. Ghareghani and H. Maimani, The
Kernels of The Incidence Matrices of Graphs Revisited, Linear
Algebra and its Applications 414 (2006), 617-625.

[6] J. Akiyama and M. Kano, Factors and Factorizations of Graphs-a
survey, Journal of Graph Theory 9 (1985), 1-42.

[7] A. Bouchet, Nowhere-Zero Integral Flows on a Bidirected
Graph, J. Combin. Theory, Ser. B 34 (1983), 279-292.

[8] R. Diestel, Graph Theory, Third Ed., Springer, Heidelberg, 2005.

[9] M. DeVos, Flows on Bidirected Graphs, Princeton University Press,
Princeton, N.J., 2004.

[10] L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University
Press, Princeton, N.J., 1962.

[11] A. Khelladi, Nowhere-zero integer chains and flows in bidirected
graphs, J. Combin. Theory, Ser. B 43 (1987), 95-115.

[12] E. Lˆe, Graph Flows and the Zero-Sum Conjecture, Pomona College,
Claremont, C.A., 2010.

[13] J. Petersen, Die Theorie der regularen graphs, Acta Math(15)
(1891), 193-220.

[14] P.D. Seymour, Nowhere-Zero 6-Flows, J. Combin. Theory, Ser. B 30
(1981), 130-135.

[15] T.M. Wang and S.W. Hu, On Zero-Sum Minimum Flow Numbers,
Submitted, 2012.

[16] T.M. Wang and S.W. Hu, Flow Number of Zero-Sum Flow, the 6th
International Frontiers of Algorithmics Workshop (FAW 2012, Beijing,
China), Lecture Notes in Computer Science(LNCS) 7285, pp. 269-278,
2012 (EI).

[17] T.M.Wang and S.W. Hu, Constant Sum Flows in Regular Graphs,
the 5th International Frontiers of Algorithmics Workshop (FAW 2011,
Jinhua, China), Lecture Notes in Computer Science(LNCS) 6681, pp.
168-175, 2011 (EI).

[18] T.M. Wang and T.B. Reynolds, Group Magic Sums of Regular
Graphs, submitted, 2010.

[19] T.M. Wang and C.M. Lin, Magic Sum Spectra of Group Magic
Graphs, India-Taiwan Conference on Discrete Mathematics (2009).

[20] T.M. Wang and C.M. Lin, On Zero Magic Sums of Integer Magic
Graphs, accepted by Ars Combinatoria, 2009.

[21] D. B. West, Introduction to Graph Theory, 2nd edn, Prentice Hall,
Englewood Cliffs, 2001.

[22] R. Xu and C. Q. Zhang, On flows in bidirected graphs, Discrete
Mathematics 299 (2005),335-343.

[23] C.Q. Zhang, Circular Flows of Nearly Eulerian Graphs and
Vertex-Splitting, Journal of Graph Theory 40 (2002), 147-161.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top