有向图Hamilton性质的研究
|
摘要
本文主要进行有向图Hamilton性质的研究。在JorgenBang—Jense「7」提出了有向图为有向Hamilton图的两个新充分条件及徐尚进副教授「11」提出有向图为哈密顿图的—个充要条件等前人所研究的主要结果的基础上，根据大量的图形特征以及有向图的邻接矩阵的特性，提出有向图以及严格有向二部图具有有向Hamilton路或者为有向Hamilton图的度充分条件，还提出利用有向图的邻接矩阵去研究有向图的Hamilton性质，进而利用图论的相关知识点以及代数学等给出相应地论证过程。第1章，主要论述了有向图及有向图的Hamilton性质的相关结果，并对本论文的研究过程及相关结果做了系统地论述。第2章，主要论述了在后面所得到的结果中需要的术语和标号，以及引理，并且给出已知的一系列结果。第3章，主要得出：判断有向图具有Hamilton路的度充分条件，其中包括严格有向二部图具有Hamilton路的度充分条件，一般有向图具有Hamilton路的度充分条件；判断有向图为Hamilton图的度充分条件，其中包括严格有向二部图为Hamilton图的度充分条件，正则有向图为Hamilton图的度充分条件。最后，对有向图的这两个方面进行了独立性分析以及对这两方面的联系进行了论述。第4章，利用代数学的有关知识，对有向图的邻接矩阵进行分析，得出有向图具有有向Hamilton路的充分条件，必要条件，充要条件；得出有向图为有向Hamilton图的充分条件，必要条件，充要条件。最后，对这两方面的联系进行了论述。第5章，对前面所论述的内容进行了总结，并提出今后需要对有向图做进一步的讨论，进一步在上述所研究的基础上提出猜想。
In this paper, the Hamiltonian qualities in Digraph are studied. On the basis of two new sufficient conditions brought up by Jorgen Bang-Jensen[7] that Digraph would be directed Hamiltonian graph and a sufficient and essential condition brought up by an associate professor Xu Shangjin[ll] that Digraph would be directed Hamiltonian graph and results of other forfathers, the sufficient conditions zbout degree of Digraph and strictly directed Bipartite graph with directed Hamiltonian path or to be directed Hamiltonian graph are shown. Also the Hamitonian qualities in Digraph are shown by making use of Adjacent matrix of Digraph. Finally the correspondent proofs are shown by uae of the correspondent contents of Graph Theory and Algebra. In the first chapter, digraph and correspondent results of Hamiltonian qualities in digraph are shown. In this paper, the studied
process and correspondent results are indicated in detail. In the second chapter, technical terms and signs, lemmas and a series of known results in following Chapters are shown. In the third chapter, the following results are obtained. The sufficient conditions about degree of Digraph with directed Hamiltonian path are given (The results include strictly directed Bipartite graph with Hamiltonian path and general digraph with Hamiltonian path). The sufficient conditions about degree of Digraph to be directed Hamiltonian graph are given (The results include strictly directed Bipartite graph to be Hamiltonian graph and regular digraph to be Hamiltonian graph). Finally, the independent analyses and the connections of the two aspects of digraph is discussed. In the forth chapter, the adjacency matrices of digraphs by
using Algebra are analied. The sufficient conditions,the essential conditions, the sufficient and essential conditions of Digraph with directed Hamiltonian paths or to be directed Hamiltonian graphs are obtained. Finally, the connections of the two aspects
of digraph are discussed. In the fifth chapter, we sum up all the results and raise further discusses about
digraph in future and raise new guesses above the known results.
In this paper, the Hamiltonian qualities in Digraph are studied. On the basis of two new sufficient conditions brought up by Jorgen Bang-Jensen[7] that Digraph would be directed Hamiltonian graph and a sufficient and essential condition brought up by an associate professor Xu Shangjin[ll] that Digraph would be directed Hamiltonian graph and results of other forfathers, the sufficient conditions zbout degree of Digraph and strictly directed Bipartite graph with directed Hamiltonian path or to be directed Hamiltonian graph are shown. Also the Hamitonian qualities in Digraph are shown by making use of Adjacent matrix of Digraph. Finally the correspondent proofs are shown by uae of the correspondent contents of Graph Theory and Algebra. In the first chapter, digraph and correspondent results of Hamiltonian qualities in digraph are shown. In this paper, the studied
process and correspondent results are indicated in detail. In the second chapter, technical terms and signs, lemmas and a series of known results in following Chapters are shown. In the third chapter, the following results are obtained. The sufficient conditions about degree of Digraph with directed Hamiltonian path are given (The results include strictly directed Bipartite graph with Hamiltonian path and general digraph with Hamiltonian path). The sufficient conditions about degree of Digraph to be directed Hamiltonian graph are given (The results include strictly directed Bipartite graph to be Hamiltonian graph and regular digraph to be Hamiltonian graph). Finally, the independent analyses and the connections of the two aspects of digraph is discussed. In the forth chapter, the adjacency matrices of digraphs by
using Algebra are analied. The sufficient conditions,the essential conditions, the sufficient and essential conditions of Digraph with directed Hamiltonian paths or to be directed Hamiltonian graphs are obtained. Finally, the connections of the two aspects
of digraph are discussed. In the fifth chapter, we sum up all the results and raise further discusses about
digraph in future and raise new guesses above the known results.
引文
[1] [美]F·哈拉里．著．《图论》．上海科学技术出版社(1968)．
[2] 杜瑞甫．编．《运筹图论》，北京航空航天大学出版社(1989)．
[3] 王树禾．编著，《图论及其算法》，中国科学技术大学出版社(1990)．
[4] 宋增民．编著．《图论与网络算法》．东南大学出版社(1990)．
[5] [美]J.A.邦迪．U.S.R.默蒂．著．《图论及其应用》．科学出版社(1984)．
[6] 田丰．马仲蕃．编著．《图与网络流理论》．科学出版社(1987)．
[7] Jorgen Bang-Jensen,Yubao Guo,AndersYeo ,A new sufficient condition for a digraph to be Hamilton ,Discrete Applied Mathematics 95(1999)61-72.
[8] V.K.BALAKRISHNAN, ph.D. XSCHAUM'S OUTLINE OF THEORY and PROBLEMS OF GRAPH THEORY,Suzanne Rapcavage (1997).
[9] Jonathan Gross and Jan Yellen, P. CM. Graph theory and its Applications,Printed in the United States of America (1999).
[10] Wang Jianzhong, THE STRUCTURE OF POWERS OF BOOLEAN MATRICES, Athesis submitted for the degree of Doctor of Philosophy of Peking University, March, 1996.
[11] Wang Jianzhong, A Sufficient Condition for Hamiltonian Cycles in Bipartite Tournaments, Austrslasian Journal of Combinatorics 5(1992) ,pp. 299-304.
[12] Joanzhong Wang, Long cycles in bipartite tournaments, Discrete Mathestics 148(1996)217-225.
[13] 王建中，弧哈密顿竞赛图的一个性质，自然杂志6卷11期．
[14] 王建中，异类具有强(p-1)—路连通性而不具有强(p-2)—路连通性的竞赛图，湖南数学年刊，第三卷第1期1983年6月．
[15] 王建中，何曙光，正则二部竞赛图的弧泛贿赂性质，科学通报，1987年．
[16] 王建中，弧哈密吨竞赛图的一个性质，应用数学学报．
[17] Jorgen Bang-Jensensen,Longest Paath and Cycles in extended Locally Semicomplete Digraph,Institut for Matemstik og Datalogi Odense Universitet Preprints 1993,No.53.
[18]Jorgen Bang-Jensensen,Finding Maximum Weight Paths and Cycles in Φ-Decomposable Digraphs,Using Flows in Networks,Institut for Matemstik og Datalogi Odense Universitet Preprints 1993,No.51.
[19]G.Gutin, Cycles and Paths in Semicomplete Multipartite Digraphs,Theorems,and Algorithms:A Survey, Jourmal of Graph Theoty, vol.19,No.4.481-505(1995).
[20]Jorgen Bang-Jensensen, Paths,Trees,Cycles and Other Subgraphs of Semicomplete Digraph:A Survey, Institut for Matemstik og Datalogi Odense Universitet Preprints 1994,Nr.14.
[21]Zhang Ke Min, Song Zeng Min, CYCLES IN DIGR. AP HS—A SURVEY, Journal of Nanjing University, Vol.27,Oct.1991.
[22]王建中，布尔矩阵的幂结构，博士研究生学位论文，1996．5．
[23]M.C.HEYDEMANN, COMMUNICATION ON CYCLES AND PATHS IN DIGRAPHS,Discrete Mathematics 31(1980)217-219.
[24]刘新，n连通、κ临界有向图的性质，新疆大学学报(自然科学版)，第8卷第1期，1991年2月．
[25]徐明耀等著，《有限群导论》，科学出版社(1999)．
[26]徐尚进，有向图具有哈密顿圈的—个充要条件，Journal of Guangxi University(Nat SciEd)(1999.6).
[27]北京大学数学系几何与代数教研室代数小组编，《高等代数》(第二版)，高等教育出版社(1987)．
[28]王朝瑞编著，《图论》(第二版)，北京理工大学出版社(1997)．
[29]熊全淹编著，《近世代数》，武汉大学出版社(1990)．
[30]张克民，林国宁，张忠辅，《图论及其应用》习题解答，清华大学出版社(1998)．
[31]樊珲，钱吉林，刘恒，穆汉林等主编，《代数学辞典》，华中师范大学出版社(1994．6)．
[32]Zhou Bo. The Upper Generalized Exponent of a Digraph. 数学进展(2000 年12月).
[33]姚源果，用矩阵判断哈密顿图的一个充要条件，广西民族学院学报(自然科学报)(2001年2月)．9-10．
[34]王锋，一类在三次多项式扰动下的Hamilton系统的极限环，江汉大学学报(2000年12月)．62-65．
[35]赵克文，Katona和Kleitman定理的推广，贵州大学学报(自然科学版)(2000年8月)．178-180．
[36]谭尚旺，张德龙，多部有向图的最大特征值，数学理论与应用．2000年3月．69-71．
[37]丁孝全，有向扇形是优美有向图，聊城师院学报(自然科学科学版)，2001年3月．103-104．
[38]王红丽，梁怀学，刘春峰，图的线图是Hamiltonian的一个充分条件，松辽学刊(自然科学版)．2000年8月．9-12．
[39]吕志宏，刘迎捷，有向连接图中节点可达的矩阵行取1算法，浙江工业大学学报，2000年9月280-282．
[40]张运清等，一类有向图的可嵌入性，陕西师范大学学报(自然科学版)，2000年12月，19-22．
[41]赵礼峰，强正则图的一些性质，应用数学，2000．13(4)；82-84．
[42]谭尚旺等，有向图和弱正则有向图补图的特征多项式的计算方法，数学杂志，Vol．20(2000)No．4．421-426．
[43]Gregory Gutin,Anders Yeo,Quasi-Hamiltonicity:A Series of Necessary Conditions for a Digraph to Be Hamiltonian,Journal of Combinatorial Theory, Series B 78,232-242(2000).
[44]John W.Kennedy, Louis V. Quintas,GRAPH THEORY NOTES OF NEW YORK(XXXIX),New York Academy of Sciences(2000).
[45]John W.Kennedy, Louis V.Quintas,GRAPH THEORY NOTES OF NEW YORK(XLI),New York Academy of Sciences(2001).
[46]Stephan Brandt, 9-Connected Claw-Free Graoh Are HamiltonConnected, Journal of Combinatorial Theory. Series B75.167-173(1999).
[47]R.FAUDREE~*, FORBIDDEN SUBGRAPHS,CLOSURE AND HAMILTONIAN PROPERTIES-RECENT RESUILS,Graph Theory and Combinatorial Biology.(1999)9-25.
[48]Rao Li,A Fan-type conditon for claw-free graphs to be Hamilton,Discrete Mathematics 219(2000)195-205.
[49]B(?)la Bollob(?)s,etc. Closure and Hamiltonian-connecitivity of clawfree graphs,Discrete Mathematics 195(1999)67-80.
[50]H.Trommel, etc. Pancyclicity of claw-free hamiltonian graphs,Discrete Mathematics 197/198(1999)781-789.
[51] Robin Thomas and Xingxing Yu,Five-Connectes Toroidal Graphs Are Hamiltonian,Journal of Combinatorial Theory.Series B 69． 79-96(1997) .
[52] Bing Weit and Yongjin Zhu,Hamitonian k-Factors in Graph journal of graph theory,24(1997) 217-227．
[53] Lenhard L.Ng,Hamiltonian decomposition of complete regular multipartite digraphs,Discrete Mathematics 177(1997) 279-185．
[54] Qi Fan Yang,Rainer E.Burkard,Eranda Cela,Gerhard J.Woeginger,Hamiltonian cycles in circulant digraphs with two stripes,Discrete Mathematics 176(1997) 233-254．
[55] 马美杰，董俊超，二部图是哈密顿的-个充分条件，烟台大学学报(自然科 学与工程版)，1999年10月第12卷第4期．242-244．
[56] Xu junming,The Connectivity of Generalized de Bruijn Digraphs,中国科学技术大学学报，第29卷第3期1999年6月，311-315．
[57] Bela Bollobas and Andrew Thomsaon,On the Girth of Hamiltonian Weakly Pancyclic Graphs,Journal of graph theory 26(1997) 166-173．
[58] Wang Jianzhong,THE STRUCTURE OF POWERS OF BOOLEAN MATRICES,Athesis submitted for the degree of Doctor of Philosophy of Peking University,March,1996．
[2] 杜瑞甫．编．《运筹图论》，北京航空航天大学出版社(1989)．
[3] 王树禾．编著，《图论及其算法》，中国科学技术大学出版社(1990)．
[4] 宋增民．编著．《图论与网络算法》．东南大学出版社(1990)．
[5] [美]J.A.邦迪．U.S.R.默蒂．著．《图论及其应用》．科学出版社(1984)．
[6] 田丰．马仲蕃．编著．《图与网络流理论》．科学出版社(1987)．
[7] Jorgen Bang-Jensen,Yubao Guo,AndersYeo ,A new sufficient condition for a digraph to be Hamilton ,Discrete Applied Mathematics 95(1999)61-72.
[8] V.K.BALAKRISHNAN, ph.D. XSCHAUM'S OUTLINE OF THEORY and PROBLEMS OF GRAPH THEORY,Suzanne Rapcavage (1997).
[9] Jonathan Gross and Jan Yellen, P. CM. Graph theory and its Applications,Printed in the United States of America (1999).
[10] Wang Jianzhong, THE STRUCTURE OF POWERS OF BOOLEAN MATRICES, Athesis submitted for the degree of Doctor of Philosophy of Peking University, March, 1996.
[11] Wang Jianzhong, A Sufficient Condition for Hamiltonian Cycles in Bipartite Tournaments, Austrslasian Journal of Combinatorics 5(1992) ,pp. 299-304.
[12] Joanzhong Wang, Long cycles in bipartite tournaments, Discrete Mathestics 148(1996)217-225.
[13] 王建中，弧哈密顿竞赛图的一个性质，自然杂志6卷11期．
[14] 王建中，异类具有强(p-1)—路连通性而不具有强(p-2)—路连通性的竞赛图，湖南数学年刊，第三卷第1期1983年6月．
[15] 王建中，何曙光，正则二部竞赛图的弧泛贿赂性质，科学通报，1987年．
[16] 王建中，弧哈密吨竞赛图的一个性质，应用数学学报．
[17] Jorgen Bang-Jensensen,Longest Paath and Cycles in extended Locally Semicomplete Digraph,Institut for Matemstik og Datalogi Odense Universitet Preprints 1993,No.53.
[18]Jorgen Bang-Jensensen,Finding Maximum Weight Paths and Cycles in Φ-Decomposable Digraphs,Using Flows in Networks,Institut for Matemstik og Datalogi Odense Universitet Preprints 1993,No.51.
[19]G.Gutin, Cycles and Paths in Semicomplete Multipartite Digraphs,Theorems,and Algorithms:A Survey, Jourmal of Graph Theoty, vol.19,No.4.481-505(1995).
[20]Jorgen Bang-Jensensen, Paths,Trees,Cycles and Other Subgraphs of Semicomplete Digraph:A Survey, Institut for Matemstik og Datalogi Odense Universitet Preprints 1994,Nr.14.
[21]Zhang Ke Min, Song Zeng Min, CYCLES IN DIGR. AP HS—A SURVEY, Journal of Nanjing University, Vol.27,Oct.1991.
[22]王建中，布尔矩阵的幂结构，博士研究生学位论文，1996．5．
[23]M.C.HEYDEMANN, COMMUNICATION ON CYCLES AND PATHS IN DIGRAPHS,Discrete Mathematics 31(1980)217-219.
[24]刘新，n连通、κ临界有向图的性质，新疆大学学报(自然科学版)，第8卷第1期，1991年2月．
[25]徐明耀等著，《有限群导论》，科学出版社(1999)．
[26]徐尚进，有向图具有哈密顿圈的—个充要条件，Journal of Guangxi University(Nat SciEd)(1999.6).
[27]北京大学数学系几何与代数教研室代数小组编，《高等代数》(第二版)，高等教育出版社(1987)．
[28]王朝瑞编著，《图论》(第二版)，北京理工大学出版社(1997)．
[29]熊全淹编著，《近世代数》，武汉大学出版社(1990)．
[30]张克民，林国宁，张忠辅，《图论及其应用》习题解答，清华大学出版社(1998)．
[31]樊珲，钱吉林，刘恒，穆汉林等主编，《代数学辞典》，华中师范大学出版社(1994．6)．
[32]Zhou Bo. The Upper Generalized Exponent of a Digraph. 数学进展(2000 年12月).
[33]姚源果，用矩阵判断哈密顿图的一个充要条件，广西民族学院学报(自然科学报)(2001年2月)．9-10．
[34]王锋，一类在三次多项式扰动下的Hamilton系统的极限环，江汉大学学报(2000年12月)．62-65．
[35]赵克文，Katona和Kleitman定理的推广，贵州大学学报(自然科学版)(2000年8月)．178-180．
[36]谭尚旺，张德龙，多部有向图的最大特征值，数学理论与应用．2000年3月．69-71．
[37]丁孝全，有向扇形是优美有向图，聊城师院学报(自然科学科学版)，2001年3月．103-104．
[38]王红丽，梁怀学，刘春峰，图的线图是Hamiltonian的一个充分条件，松辽学刊(自然科学版)．2000年8月．9-12．
[39]吕志宏，刘迎捷，有向连接图中节点可达的矩阵行取1算法，浙江工业大学学报，2000年9月280-282．
[40]张运清等，一类有向图的可嵌入性，陕西师范大学学报(自然科学版)，2000年12月，19-22．
[41]赵礼峰，强正则图的一些性质，应用数学，2000．13(4)；82-84．
[42]谭尚旺等，有向图和弱正则有向图补图的特征多项式的计算方法，数学杂志，Vol．20(2000)No．4．421-426．
[43]Gregory Gutin,Anders Yeo,Quasi-Hamiltonicity:A Series of Necessary Conditions for a Digraph to Be Hamiltonian,Journal of Combinatorial Theory, Series B 78,232-242(2000).
[44]John W.Kennedy, Louis V. Quintas,GRAPH THEORY NOTES OF NEW YORK(XXXIX),New York Academy of Sciences(2000).
[45]John W.Kennedy, Louis V.Quintas,GRAPH THEORY NOTES OF NEW YORK(XLI),New York Academy of Sciences(2001).
[46]Stephan Brandt, 9-Connected Claw-Free Graoh Are HamiltonConnected, Journal of Combinatorial Theory. Series B75.167-173(1999).
[47]R.FAUDREE~*, FORBIDDEN SUBGRAPHS,CLOSURE AND HAMILTONIAN PROPERTIES-RECENT RESUILS,Graph Theory and Combinatorial Biology.(1999)9-25.
[48]Rao Li,A Fan-type conditon for claw-free graphs to be Hamilton,Discrete Mathematics 219(2000)195-205.
[49]B(?)la Bollob(?)s,etc. Closure and Hamiltonian-connecitivity of clawfree graphs,Discrete Mathematics 195(1999)67-80.
[50]H.Trommel, etc. Pancyclicity of claw-free hamiltonian graphs,Discrete Mathematics 197/198(1999)781-789.
[51] Robin Thomas and Xingxing Yu,Five-Connectes Toroidal Graphs Are Hamiltonian,Journal of Combinatorial Theory.Series B 69． 79-96(1997) .
[52] Bing Weit and Yongjin Zhu,Hamitonian k-Factors in Graph journal of graph theory,24(1997) 217-227．
[53] Lenhard L.Ng,Hamiltonian decomposition of complete regular multipartite digraphs,Discrete Mathematics 177(1997) 279-185．
[54] Qi Fan Yang,Rainer E.Burkard,Eranda Cela,Gerhard J.Woeginger,Hamiltonian cycles in circulant digraphs with two stripes,Discrete Mathematics 176(1997) 233-254．
[55] 马美杰，董俊超，二部图是哈密顿的-个充分条件，烟台大学学报(自然科 学与工程版)，1999年10月第12卷第4期．242-244．
[56] Xu junming,The Connectivity of Generalized de Bruijn Digraphs,中国科学技术大学学报，第29卷第3期1999年6月，311-315．
[57] Bela Bollobas and Andrew Thomsaon,On the Girth of Hamiltonian Weakly Pancyclic Graphs,Journal of graph theory 26(1997) 166-173．
[58] Wang Jianzhong,THE STRUCTURE OF POWERS OF BOOLEAN MATRICES,Athesis submitted for the degree of Doctor of Philosophy of Peking University,March,1996．