几类图分解的存在性研究
发布时间：2018-08-21 07:25
【摘要】：令H为一个图,G为H的一个给定的子图.图H的G分解,是指将图H分解成一些子图,使得所有子图的边集划分H的边集,且每个子图同构于图G.图分解问题在密码理论、实验设计、X-射线衍射晶体学、计算机与通讯网络等其它领域有重要的应用.随着图论逐渐发展成为比较系统的一门学科之后,人们发现许多组合问题都与图分解问题有密切联系.本文利用组合设计理论,借助递归构造和直接构造的方法,给出了几类图分解存在的充分必要条件.本文结构组织如下.第一章:介绍了图分解的研究背景、概念及一些已知结论,并给出了本文的主要结果.第二章:为建立下文中几类图分解的存在性,给出了一些递归构造.第三章:利用递归构造和直接构造方法,建立了 v阶λ-重P-设计到v阶λ-重P4最大填充的变形存在的充分必要条件:λv(- 1)三0 (mod 8)且v≥5.第四章:利用递归构造和直接构造方法,建立了v阶λ-重K1,4-设计到v阶λ-重K1,3-最大填充的变形存在的充分必要条件:λv(v-1)≡0 (mod 8)且v≥ 5.第五章:利用递归构造和直接构造方法,建立了 v阶λ-重C4 + e-设计到v阶λ-重P5-设计的变形存在的充分必要条件:λ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
本文链接：https://www.wllwen.com/kejilunwen/yysx/2194981.html
