幾類圖分解的存在性研究
發(fā)布時間：2018-08-21 07:25
【摘要】：令H為一個圖,G為H的一個給定的子圖.圖H的G分解,是指將圖H分解成一些子圖,使得所有子圖的邊集劃分H的邊集,且每個子圖同構(gòu)于圖G.圖分解問題在密碼理論、實驗設(shè)計、X-射線衍射晶體學(xué)、計算機與通訊網(wǎng)絡(luò)等其它領(lǐng)域有重要的應(yīng)用.隨著圖論逐漸發(fā)展成為比較系統(tǒng)的一門學(xué)科之后,人們發(fā)現(xiàn)許多組合問題都與圖分解問題有密切聯(lián)系.本文利用組合設(shè)計理論,借助遞歸構(gòu)造和直接構(gòu)造的方法,給出了幾類圖分解存在的充分必要條件.本文結(jié)構(gòu)組織如下.第一章:介紹了圖分解的研究背景、概念及一些已知結(jié)論,并給出了本文的主要結(jié)果.第二章:為建立下文中幾類圖分解的存在性,給出了一些遞歸構(gòu)造.第三章:利用遞歸構(gòu)造和直接構(gòu)造方法,建立了 v階λ-重P-設(shè)計到v階λ-重P4最大填充的變形存在的充分必要條件:λv(- 1)三0 (mod 8)且v≥5.第四章:利用遞歸構(gòu)造和直接構(gòu)造方法,建立了v階λ-重K1,4-設(shè)計到v階λ-重K1,3-最大填充的變形存在的充分必要條件:λv(v-1)≡0 (mod 8)且v≥ 5.第五章:利用遞歸構(gòu)造和直接構(gòu)造方法,建立了 v階λ-重C4 + e-設(shè)計到v階λ-重P5-設(shè)計的變形存在的充分必要條件:λv(- 1)≡0 (mod 40) 且v≥ 5.
[Abstract]:Let H be a given subgraph of a graph G is H. The G decomposition of graph H means that the graph H is decomposed into some subgraphs so that the edge sets of all subgraphs are partitioned into the edge sets of H, and each subgraph is isomorphic to the graph G. The problem of graph decomposition has important applications in cryptography theory, experimental design, X-ray diffraction crystallography, computer and communication network, etc. With the gradual development of graph theory into a more systematic subject, it is found that many combinatorial problems are closely related to graph decomposition problems. In this paper, the sufficient and necessary conditions for the existence of several classes of graph decomposition are given by using the combinatorial design theory and the methods of recursive construction and direct construction. The structure of this paper is as follows. Chapter 1: the research background, concept and some known conclusions of graph decomposition are introduced, and the main results of this paper are given. Chapter 2: in order to establish the existence of some classes of graph decomposition, some recursive constructions are given. In chapter 3, by means of recursive construction and direct construction, a necessary and sufficient condition for the existence of 位 -heavy P- design of order v to the maximum filling of order 位 -heavy P4 is established: 位 _ v (-1) 30 (mod _ 8) and v 鈮，
本文編號：2194981
[Abstract]:Let H be a given subgraph of a graph G is H. The G decomposition of graph H means that the graph H is decomposed into some subgraphs so that the edge sets of all subgraphs are partitioned into the edge sets of H, and each subgraph is isomorphic to the graph G. The problem of graph decomposition has important applications in cryptography theory, experimental design, X-ray diffraction crystallography, computer and communication network, etc. With the gradual development of graph theory into a more systematic subject, it is found that many combinatorial problems are closely related to graph decomposition problems. In this paper, the sufficient and necessary conditions for the existence of several classes of graph decomposition are given by using the combinatorial design theory and the methods of recursive construction and direct construction. The structure of this paper is as follows. Chapter 1: the research background, concept and some known conclusions of graph decomposition are introduced, and the main results of this paper are given. Chapter 2: in order to establish the existence of some classes of graph decomposition, some recursive constructions are given. In chapter 3, by means of recursive construction and direct construction, a necessary and sufficient condition for the existence of 位 -heavy P- design of order v to the maximum filling of order 位 -heavy P4 is established: 位 _ v (-1) 30 (mod _ 8) and v 鈮，
本文編號：2194981
本文鏈接：http://sikaile.net/kejilunwen/yysx/2194981.html
最近更新
教材專著
