On Hamilton Decompositions

格式：pdf
大小：144.35 KB
文档页数：10

下载文档原格式

MBA百科

对称博弈
• 定义一：所谓对称博弈对称博弈是指群体中个体无角色区分的博对称博弈弈，在进化博弈中，不同角色一般按个体所能够选择的纯策略集合是相同还是不相同来区分的，因此对称博弈中所有的个体都有相同的行动空间[1]。 • 定义二：在博弈论，如果博弈的收益只依赖于选手所选择的策略而不依赖于进行博弈的选手，这类博弈称为对称博弈。 • 例如，在囚徒困境的博弈中，囚徒都选择认罪的结果为都判刑10年，都选择不认罪的结果为都判刑1年，一个选择认罪一个不认罪的结果分别为判刑20年与释放。在这个博弈中，囚徒最终判刑的年数只要他选择认罪与否有关，而与他的身份无关，这就是一个对称博弈。用表格表示如下。
钻石与水悖论
• 钻石与水悖论钻石与水悖论首次由亚当·斯密在他的著作国富论里提出，也称作价值价值悖论（悖论（paradox of value）。此一理论在台湾教科书中常被称作，钻石）与水的矛盾。 • 众所周知，钻石对于人类维持生存没有任何价值，然而其市场价值非常高。相反，水是人类生存的必需品，其市场价值却非常低。这种强烈的反差就构成了这个悖论。为什么会有这样的现象呢？若不考虑市场上的其他因素，沙漠地区的水比钻石贵，或者是需求面的因素。就供给面来说，水的数量非常大，且几乎随处可见（如果不考虑荒漠干旱地区，地球上几乎处处都有水，包含大气层中的水汽）；而钻石呢，是蕴藏在地表底下，且必须经过时间与适当的条件产生（如果不考虑人工钻石而单纯考虑自然钻石），供给非常的少，因此水供给大，而钻石供给少，故会产生这样的现象。 • 对此，亚当·斯密在《国富论》中指出： • 没什么东西比水更有用；能用它交换的货物却非常有限；很少的东西就可以换到水。相反，钻石没有什么用处，但可以用它换来大量的货品。 • 钻石与水的悖论，台湾所称的钻石与水的矛盾，即是中国俗谚中的：物以稀为贵。

Hamilton力学的辛算法

1 x 3x2 x3 x4 2 28 84 1680
1 x 3x2 x3 x4 2 28 84 1680
精度
2阶
4阶
6阶
8阶
*： “(1,1) 逼近”g11 x ，就是Euler中点格式。
24
第24页/共44页
可分线性Hamilton体系的交叉显式辛格式
H q,p 1 pTTp 1 qT Vq
a,a 0
然后就可以给出向量的长度、正交、单位向量等概念。 6 第6页/共44页
辛空间（Simplectic Space）
具有如下内积定义的线性空间W为“辛空间” 。这种内积称为“辛内积”。
• 反对称性：a,b b,a • 双线性： a1 a2,b a1,b a2,b
a,b1 b2 a,b1 a,b2 • 非简并性：若向量a对于W中的任意向量b均
h 2
Vp m 1
qm
h 2
Vpm
p
m1
h 2
Tq m 1
pm
h 2
Tqm
h 2
V
1n
1n
h 2
T
pm1 qm1
h 2
1n
V
第21页/共44页
1n
p
h 2
T21q
m m
z m1
pm1
qm1
hV 2 1n
1n
1
h 2
V
h 2
T
1n
1n
a, b aT J2nb a1T
aT2 0 1n
1n 0
b1 b2
aT2
a1T b1
b2
a1T b2
aT2b1
n i 1
aibni anibi

三种常用趋势周期分解方法的比较

三种常用趋势周期分解方法的比较本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March第1组，数量经济理论与方法文章字数：8967个三种常用趋势周期分解方法的比较孙晓涛*（华中科技大学经济学院）摘要：本文选取不可观测成分模型分解、BN分解和HP滤波等三种常用的趋势周期分解方法，从它们的分解原理方面进行了对比。

虽然这三种方法的理论出发点是不同的，但本文的研究发现：不可观测成分模型分解和BN分解可以统一在一个扩展的不可观测成分模型框架内；HP滤波可以看作一个受约束的不可观测成分模型分解。

本文同时应用我国的GDP序列对以上结论进行了验证。

本文的研究还发现，我国GDP序列中的趋势成分和周期成分间存在不完全的负相关，这与传统的不可观测成分模型分解和BN分解的设定是不同的。

关键词趋势周期分解 UC模型 BN分解 HP滤波中图分类号文献标识码 AComparison of Three Commonly Used Trend-Cycle Decompositions Abstract: This paper selects three commonly used trend-cycle decompositions, including unobserved components (UC) model decomposition, BN decomposition and HP filter, and compares these methods in theoretical aspects. Although the starting points of these methods are different, this study shows that UC model decomposition and BN decomposition can be unified in a broader UC model decomposition, and HP filter is consistent with a constrained UC model decomposition. At the same time, Chinese GDP is used to verify the above conclusions. Different from traditional UC model decomposition and BN decomposition, this study also finds that the trend and cycle components of Chinese GDP have non-perfect negative correlation.Key words: Trend-Cycle Decomposition; UC Model; BN Decompositions; HP Filter一、引言* 孙晓涛，男，1981年11月生，华中科技大学数量经济学博士研究生在读，中国数量经济学会会员。

Fronts propagating with curvature dependent speed Algorithms Based on Hamilton-Jacobi Formulations

reaching out into the unburnt gas somehow propagate slower than do concave regions which are hot gases surrounding a small unburnt pocket. At the same time, particles along the ﬂame front undergo an increase in volume as they burn, creating a jump in velocity across the ﬂame front. This discontinuity in the velocity ﬁeld creates vorticity along the burning ﬂame, which can be related to the local curvature, and this new vorticity ﬁeld contributes to the advection of the propagating ﬂame. Thus, there are at least two distinct ways in which the speed of the moving ﬂame depends on the local curvature. Typically, there have been two types of numerical algorithms employed in the solution of such problems. The ﬁrst parameterizes the moving front by some variable and discretizes this parameterization into a set of marker points [39]. The positions of the marker points are updated in time according to approximations to the equations of motion. Such techniques can be extremely accurate in the attempt to follow the motions of small perturbations. However, for large, complex motion, several problems soon occur. First, marker particles come together in regions where the curvature of the propagating front builds, causing numerical instability unless a regridding technique is employed. The regridding mechanism usually contains a error term which resembles diffusion and dominates the real effects of curvature under analysis. Secondly, such methods suffer from topological problems; when two regions "burn" together to form a single one, ad-hoc techniques to eliminate parts of the boundary are required to make the algorithm work. Other algorithms commonly employed fall under the category of "volume of ﬂuid " techniques, which, rather than track the boundary of the propagating front, track the motion of the interior region. An example of this type of algorithm is SLIC [26]. In these algorithms, the interior is discretized, usually by employing a grid on the domain and assigning to each cell a "volume fraction" corresponding to the amount of interior ﬂuid currently located in that cell. An advantage of such techniques is that no new computational elements are required as the calculation progresses (unlike the parameterization methods), and complicated topological boundaries are easily handled, see [4,32]. Unfortunately, it is difﬁcult to calculate the curvature of the front from such a representa-

A High-Order Domain Decomposition algorithm for the Heat Equation

then the sub-domain problems are solved in parallel by the√famous forth-order compact scheme.
The stability bound of the procedure is derived to be 1 +
1 2
(unk +2
−
unk )
=
r∆+
∆−
unk +
1 2
and unk+2 − 2unk+1 + unk = r∆+∆−(unk+1 − unk ).
From (??) and (??), there holds
1 2
(1
−
1 6r
)(unk +2
−
unk )
+
1 6r
(unk +1
−
unk )
domains are calculated by the classical explicit scheme, while interior values of sub-domains are
determined by the famous forth-order compact scheme. The stability and convergence for this
Denote
∆+unj
=
unj+1
− unj ,
∆−unj
=
unj
− unj−1
and
unj +
1 2
=
1 2
(unj +1

Integrated density of states and Wegner estimates for random Schrodinger Operators

INTEGRATED DENSITY OF STATES AND WEGNER ESTIMATES
99
On the other hand, the electron could be moving in an amorphous medium, in which case there is no large group of symmetries of the Hamiltonian. However, from the physical point of view it is reasonable to assume that the local structure of the medium will be translation invariant on average. This means that we consider the potential which the electron experiences as a particular realisation of a random process and assume stationarity with respect to some group of translations. Moreover, physical intuition suggests to assume that the local properties of the medium in two regions far apart (on the microscopic scale) are approximately independent from each other. Therefore the stochastic process describing the potential should have a correlation function which decays to zero, or — more precisely — should be ergodic. There are interesting models which lie between the two extreme cases of latticeperiodic and amorphous media. They still have an underlying lattice structure which is, however, modiﬁed by disorder. Probably the best studied Hamiltonian with this properties is the alloy type model. We leave its precise deﬁnition for the next paragraph and introduce here a special case on the intuitive level. Consider ﬁrst the potential Vω (x) := uk (ω, x) Each k corresponds to a nucleus sitting on a lattice point. The function uk (ω, ·) describes the atomic or nuclear potential at the site k and depends on the random parameter ω which models the diﬀerent realisations of the conﬁguration of the nuclei. If there is only one type of atom present, which has a spherically symmetric potential, all the uk (ω, ·) are the same, and Vω is periodic. Now assume that there are two kinds a and b of atoms present, which have spherically symmetric atomic potentials of the same shape, but which diﬀer in their nuclear charge numbers. In this case the potential looks like Vω (x) :=

Hamilton图的若干判定条件

Hamilton图的若⼲判定条件摘要Hamilton回路判断的充分必要条件是⾄今尚未解决的⼀个难题，本⽂探讨了⼀些Hamilton图的充分条件，必要条件，并根据Hamilton图的相关性质给出了若⼲种判定Hamilton图的⽅法，同时，也给出了判定⽅法相应的实例。

关键词Hamilton图；充要条件；判定⽅法；回路；简图AbstractThe sufficient and necessary condition for judging Hamiltonian graph has been an unsettled problem for a long time. This paper mainly concerns some sufficient condition and some necessary conditions, and gives some methods for judging Hamiltonian graph based on the properties of Hamiltonian graph. Meanwhile , some examples are given.Key wordsHamiltonian graph; the sufficient and necessary condition; methods of judgement ; cycle；simple graph⽬录1．引⾔ (1)2．Hamilton图的相关概念 (2)3．Hamilton图的性质 (3)4．Hamilton图的若⼲判定⽅法 (5)5．相关的应⽤实例 (7)5.1 典型例⼦ (7)5.2 简单实例 (8)5.3 判断Hamilton图－1 (8)5.4 判断Hamilton图－2 (8)5.5 Petersen图是⾮Hamilton图的⼀个证明 (11)参考⽂献 (13)谢辞 (14)Hamilton图的若⼲判定条件Judgement of Hamiltonian Graph１.引⾔1859年，英国数学家哈密顿（Hamilton）爵⼠提出了下列周游世界的游戏：在正⼗⼆⾯体的⼆⼗个顶点上依次标记伦敦，巴黎，莫斯科，华盛顿，北京，东京等世界著名⼤城市;正⼗⼆⾯体的棱（边）表⽰连接这些城市的路线，问：能否在图中做⼀次旅⾏，从顶点到顶点，沿着边⾏⾛，经过每个城市恰好⼀次之后再回到出发点？这个问题被称为Hamilton问题。

4度Cayley图的Hamilton圈分解的新方法与理论证明

每个通道的两边是由着色 b 的边组成, 而底 (axt bt , axt +1 bt ) 和 (axt bt+1 , axt +1 bt+1 ) 是由着色 a 的边组成. 如图 1 中的途径:(1, a4 b6 , · · · , a4 b3 , a4 b2 , a5 b2 , a5 b3 , · · · , a5 b6 , a); (a2 , a6 b6 , a6 b5 , · · · , a6 , a2 b6 , a2 b5 , a2 b4 , a2 b3 , a3 b3 , a3 b4 , · · · , a3 b7 , a7 , a7 b, · · · , a7 b6 , a3 ); (a5 b2 , a5 b3 , · · · , a5 b6 , a, a2 , a6 b6 , a6 b5 , · · · , a6 b2 ); (b, b2 , · · · , b6 , a4 , a4 b, a5 b, a5 , ab6 , ab5 , · · · , ab) 均为单向通道. 显然, 在对单向通道中的 H 方进行 H 方操作时产生小的闭圈. 如对图 1 中的 H 方 H4,4 = 4 4 (a b , a5 b4 , a5 b5 , a5 b4 , a4 b4 ) 进行 H 方操作. 有闭圈 (a4 b2 , a4 b3 , a4 b4 , a5 b4 , a5 b3 , a5 b2 , a4 b2 ) 产生. 定义 2.3 设 C 为群 G 的 Cayley 图 X = Cay(G, S )(S = {a±1 , b±1 }) 的 Hamilton 圈. Cu ,Cv 为对 H 方 Hij 进行 H 方操作后, 由 C 形成的两条途径. 若 Cu 的两个端点为 Hij 的两个不相邻的顶点, Cv 的两个端点为 Hij 的另两个不相邻的顶点, 则称 Hij 对 C 具有 Q 特点. 图 2 为 G = a, b|a8 = 1, a4 = b7 , ab = ba 的 Cayley 图 X = Cay(G, S )(S = {a±1 , b±1 }) 对 H 方 H1,0 ;H4,1 ;H2,2 ;H5,3 ;H4,4 ;H5,5 操作后由着色 a 的二因子形成的 H 圈 C2 . 易知, H6,6 = (a6 b6 , a6 b7 , a7 b7 , a7 b6 , a6 b6 ) = (a6 b6 , a2 , a3 , a7 b6 , a6 b6 ) 对 C2 具有 Q 特点.

Domain decomposition methods for the steady Stokes equations

1 Nektonics, Inc., 15 Everett Street, Arlington, MA 02474-6901, U.S.A. Eleventh International Conference on Domain Decomposition Methods Editors Choi-Hong Lai, Petter E. Bj rstad, Mark Cross and Olof B. Widlund c 1999
DD METHODS FOR SSchwarz preconditioners used for standard, low-order nite element systems can also be used as preconditioners for the spectral element systems. Numerical experiments demonstrating this approach were rst presented in Pah93] in the context of solving the Poisson problem, and later analyzed in Cas97]. Similar techniques have also been used with success in order to solve the consistent pressure Poisson operator Fis97, FMTar]. Additive Schwarz methods have only recently been used for the full (inde nite) Stokes system in coupled form. In KPar], a Krylov space method such as the GMRES method is used in combination with an inde nite preconditioner based upon overlapping Schwarz techniques. The additive version of this preconditioner comprises a coarse (inde nite) Stokes system and local (inde nite) Stokes subproblems associated with the overlapping subdomains. The work in KPar] was done in the context of stable, mixed, linear nite elements. In the context of high-order spectral element methods, primarily iterative substructuring methods have been considered for the global, coupled Stokes system in the past R n96, R n98, Cas96, PW97]; the techniques reported in R n96, R n98] have also been extended to solve the steady Navier-Stokes equations in three dimensions. Recently, however, the methodology presented in KPar] has also been extended to spectral elements; see Pavar]. In this paper, we consider a new overlapping, additive Schwarz approach for the steady Stokes system in three dimensions. In contrast to the work presented in KPar] in the context of linear nite elements, and to the work in Pavar] in the context of spectral elements, we abandon the concept of considering the \full" Stokes operator for the local problems associated with the subdomains. Instead, we consider two new domain decomposition methods where the local pressure solutions are computed based upon non-overlapping techniques, while the velocity degrees-of-freedom are preconditioned either based upon overlapping methods for the local problems or by solving a global problem for the viscous system.

关于信息超图一些基本概念的注记

关于信息超图一些基本概念的注记于德玉;吉日木图【摘要】随着信息科学的发展,超图在信息科学中有着非常广泛的应用,例如网络工程、数据库理论、聚类、分子超图的识别和分子超图的结构等等.在《The Information Hypergraph Theory》一书中,信息超图的基本概念被引入,这一概念来源于信息科学的数据库理论.本文对信息超图的基本概念进行解读和补充,并得到了几个新的结果.【期刊名称】《内蒙古民族大学学报（自然科学版）》【年(卷),期】2017(032)002【总页数】3页(P98-100)【关键词】孤立点;耳朵;无圈;伴随超图;补图【作者】于德玉;吉日木图【作者单位】内蒙古民族大学数学学院,内蒙古通辽028043;内蒙古民族大学离散数学研究所,内蒙古通辽028043;内蒙古民族大学数学学院,内蒙古通辽028043;内蒙古民族大学离散数学研究所,内蒙古通辽028043【正文语种】中文【中图分类】O157.5超图是有限集合的子集系统，是离散数学中最一般的结构.早期的定理有Sperner 定理和Ramsey定理等.Duchet〔1〕概括了超图的历史原由:20世纪，公理化趋势的影响和离散数学带来的快速增长的经济利益促使科学家去发展一种有限集合族的系统的组合方法.20世纪60年代，Berge在《Graphs and Hypergraphs》中首次提出“超图”一词，并建立了无向超图理论，用拟阵来研究超图在运筹学中的应用.Erdös和Hajnal〔2〕奠定了超图的理论基础.作为普通图的推广，超图在树、圈、覆盖和染色等方面已取得一些重要结果〔3，4〕.关系数据模型是科学家研究数据库时需要解决的一个重要问题，而关系数据设计的关键是设计一个数据库图式，使信息不损失.上世纪80年代，信息学家在研究信息理论时，发现属性集R上的一个数据库图式就是R上的一个超图.进而引进了无圈超图的概念.这与传统超图的有关定义不同，称之为“信息超图”，并证明其在计算机科学和信息科学中十分有用〔5，6〕，本文基于超图的研究，给出了超图的孤立点、耳朵和有圈之间的关系，还给出了一致无圈超图的伴随超图是无圈的必要条件以及一致超图的伴随超图和补图的关系.设X是有限集合表示X的所有k-元子集构成的集合，2X表示X的所有子集构成的集合.定义2.1〔7〕是一个有限集合是V的一个子集合族，即ε⊆2V.如果和，我们称H=(V,ε)是V上的一个超图，或简称ε是一个在V上的超图，集合ε称为边集.称为ε的阶，称为ε的规模.如果ε的每条边e，都有|e|=k，则称ε是一个k-一致超图.如果k=2，则ε是一个通常的图.如果ε是由V的所有k-元子集构成的集合，则称ε是一个完全k-一致超图，记为定义2.2〔7〕一个超图ε称为不可约超图，或简单超图，如果它的任意两条边都互不包含，即∀e,e′∈ε, e≠e′，都有e\e′≠∅.下面除特别说明，所说的超图都是简单超图.定义2.3〔7〕设ε是V上的一个超图，一个顶点u∈V，如果u仅属于ε的一条边，则u被称为ε的一个孤立点.定义2.4〔7〕一条边e∈ε，如果存在另外一条边e′∈ε使得e\e′中每个顶点都是孤立点，则e称为ε的一个耳朵.特别地，如果e的所有顶点都是孤立点，则e也是一个耳朵.例如:ε={a bc,cde,efa,ace}，b，d，f都是ε的孤立点，abc，cde，efa都是ε的耳朵.定义2.5〔7〕令ε是V上的一个超图，称为ε的伴随超图，如果={V \e:e∈ε}.定义2.6〔13〕设ε是V上的一个k-一致超图，称εc为ε的补超图，如果超图ε的伴随超图和补超图概念不同.例如，则.很显然定义2.7〔12〕一个k-一致超图H是一个l-圈，如果存在H的顶点的一个循环序列使得H的每条边由k个连续的顶点组成，且每一对连续的边都恰相交于l个顶点(1 ≤l≤k-1).如果l=k-1，则H被称为一个紧圈，如果l=1，则H被称为一个松圈.下面除特别说明，所说的圈都是紧圈.引理2.8〔7〕对一个n阶m条边的约简无圈超图，有m≤n-max |e|+1.引理2.9〔7〕对一个最大n阶m条边的k-一致无圈超图，有m=n-k+1.引理2.10〔7〕一个不少于两条边的无圈超图至少有两个耳朵.无圈公理〔7〕一个超图ε可以通过重复使用下面两种运算化为空集:(a1)若x是孤立顶点，去掉x.(a2)若ei⊆ej,i≠j，去掉ei.一个等价的表述:ε可以通过重复移去耳朵变为空集.满足无圈公理的超图被称为无圈超图，否则称为有圈的.一个无圈超图的部分超图可能是有圈的.例如:ε={a bc,cde,efa,ace} 是无圈的，而是ε的部分超图，但ε′是有圈的.超图的这种性质是普通图所没有的.定理3.1若超图ε有耳朵，则ε一定有孤立点.证明由超图耳朵定义，设超图的一个耳朵，则存在另外一条边e′∈ε使得e\e′中每个顶点都是孤立点，所以ε有孤立点.注意到此定理的逆定理不一定成立.反例:设.显然ε有一个孤立点a，但是ε没有耳朵.定理3.2若超图ε无孤立点，则超图ε一定有圈.证明由定理3.1，超图ε没有孤立点，则ε没有耳朵，故由超图的无圈公理，ε不能变为空集，从而超图ε是有圈的.定理3.3设ε是一个最大的n阶k-一致无圈超图.若ε的伴随超图是一个无圈超图，则n≤2k.证明由伴随超图的定义有，n阶k-一致超图ε的伴随超图是n阶(n -k)-一致超图，且伴随超图的边数 ||与原超图的边数|ε|相等，即||= |ε|.又若是无圈的，由引理 2.8有，由引理2.9可知，最大的n阶k-一致无圈超图ε的边数|ε|=n-k+1.从而n-k+1≤k+1，即n≤2k.注意到此定理的逆定理不一定成立.反例:设，显然其伴随超图.容易验证ε是一个最大的n阶k-一致无圈超图，且满足n≤2k.但由于没有孤立点，由定理3.2，所以有圈.定理3.4设ε是n阶k-一致超图，其伴随超图和补图εc有如下关系:（1）当n≠2k时，和εc没有包含关系.（2）当n=2k时，ε⋂=∅的充分必要条件是⊆εc.证明（1）由n阶k-一致超图补图和伴随超图的定义可知，超图ε的补图εc是n 阶k-一致超图，伴随超图是n阶(n -k)-一致超图.由于n≠2k，所以n-k≠k，即伴随超图不是k-一致超图，所以和εc没有包含关系.（2）当n=2k时，ε是n阶k-一致超图，所以和εc均为n阶k-一致超图.必要性.反证法.假设⊄εc，则存在一条边e，使得e∈且e∉εc，即e∈ε，所以ε⋂≠∅.这与ε⋂=∅矛盾.充分性.反证法.假设ε⋂≠∅，设存在一条边e，使得e∈ε且e∈，由补图的定义可知，e∈且e∉εc.所以⊄εc，这与⊆εc矛盾.当n=2k时，ε⋂=∅的充分必要条件是⊆εc.〔1〕P Duchet.Hypergraphs，Handbook of combinatorics〔M〕.Beckeley:The MIT Press，1995.381-423.〔2〕Erd s P，A.Hajnal.On the chromatic number of graphs and Set systems〔J〕.Acta Math Acda sci Hungar，1966（17）:61-99.〔3〕贝尔热，卜月华.超图有限集的组合学〔M〕.南京:东南大学出版社，2002. 〔4〕B Bollobábinatorics〔M〕.Cambridge:Cambridge University Press，1986.〔5〕Beer C，Fagin R，Maier D et al.On the Desirability of Acyclic Database Schemes〔J〕.Journal of the Acm，1983，30（3）: 479-513. 〔6〕T T Lee.partII information structures of database schemes〔J〕.IEEE Transactions on Software Engineering，1987，13（10）: 1062-1072. 〔7〕王建方.超图的理论基础〔M〕.北京:高等教育出版社，2006.〔8〕吴望名.图论及其应用〔M〕.北京：科学出版社，1984.〔9〕吉日木图.图的标号及超图的分解问题的研究〔D〕.大连:大连理工大学，2006.〔10〕沙特朗，张萍.图论导引〔M〕.北京：人民邮电出版社，2007.〔11〕王建方，闫桂英.超图的圈结构〔J〕.科学通报，2001，（19）:1585-1589. 〔12〕Daniela Kuhn，Deryk Osthus.Decompositions of complete uniform hypergraphs into Hamilton Berge cycles〔J〕.Journal of Combinatorial Theory，2014，126（1）:128-135.〔13〕Chang An，S Miao.The Laplacian of the Complement of a k-uniform hypergraph〔J〕.Journal of Mathematical Study，2000，33（3）:251-260.。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

To explain our procedure of the construction of directed Hamilton circuits, which when taken together provide the desired decomposition, we discuss it first for the special case, i.e., for a leading diregular tournament on 2n + 1 = 7 points. We construct n = 3 labeled Hamilton circuits that tightly pack the leading diregular tournament on 2n + 1 = 7 points, i.e., each made up from distinct labeled directed edges such that all these directed labeled edges taken together constitute a labeled leading diregular tournament on 2n + 1= 7 points. For this to achieve we use the existence of n =3 coprime numbers ≤ 3 . Since 2n + 1 = 7 is a prime number, such numbers exist. We have {1, 2, 3} as the desired set of numbers. We form sequences of the numbers using the numbers in this set as the increment for the sequences, and further by taking the numbers in these sequences as labels of vertices which are joined by the directed edges in the same order, we form the desired Hamilton circuits as follows: Here, in these sequences the numbers (which are to be taken as suffixes of the vertex labels) are differing from next number (next vertex label) by 1mod (7) for the first sequence, by 2mod (7) for the second sequence, and by 3mod (7) for the third and the last sequence. Thus, we construct three sequences and their associated Hamilton circuits as follows: Sequence 1: (1, 2, 3, 4, 5, 6, 7, 1) Hamilton Circuit 1: v1 → v2 → v3 → v4 → v5 → v6 → v7 → v1 Sequence 2: (1, 3, 5, 7, 2, 4, 6, 1)
(i, j ) = (n + 2,1), (n + 3,1), (n + 3,2),L, (2n + 1,1), (2n + 1,2),L, (2n + 1, n) .
1
Example: We state below the adjacency matrix of the leading diregular tournament on 9 points:
2
Hamilton Circuit 2: v1 → v3 → v5 → v7 → v2 → v4 → v6 → v1 Sequence 3: (1, 4, 7, 3, 6, 2, 5, 1) Hamilton Circuit 3: v1 → v4 → v7 → v3 → v6 → v2 → v5 → v1 Remark 1.1: From the above procedure it is the availability of n = 3 numbers ≤ n, namely, {1, 2, 3}, co-prime to number ( 2n + 1) = 7, which is important! Remark 1.2: It is important to see that when the above circuits are taken together they all contain distinct directed edges and together constitute the leading diregular tournament on 2n + 1 = 7 points. Thus, these circuits tightly pack the leading diregular tournament on 2n + 1 = 7 points by Hamilton circuits as desired! Check the equal indegree and outdegree for every vertex!! 2. Hamilton Decompositions: Our idea to prove the existence of decomposition, in terms of Hamilton circuits, for an unlabeled leading diregular tournament is to construct a tight packing for a labeled copy by certain labeled Hamilton circuits which completely define the adjacencies for all the outgoing and incoming directed edges at each labeled vertex. Algorithm for construction of labeled Hamilton circuits which tightly pack into a labeled leading diregular tournament on (2n+1) points when (2n+1) is a prime number: 1) Take n co-prime numbers to given prime number (2n+1). They are α 1 = 1, α 2 = 2 , L , α n = n . 2) Construct n number of sequences of numbers such that each sequence starts with number 1 and ends with number 1 and contains in between a particular arrangement of 2n numbers from set of numbers {2, 3, …, 2n+1} as follows: Sequence 1: (1, 1+ α 1 mod( 2 n + 1) , 1+2α 1 mod( 2 n + 1) , …, 1) Sequence 2: (1, 1+ α 2 mod( 2 n + 1) , 1+2α 2 mod( 2 n + 1) , …, 1) . . . Sequence n: (1, 1+α n mod( 2 n + 1) , 1+2 α n mod( 2 n + 1) , …, 1) 3) Using the numbers in each sequence as suffixes of the vertices construct the following Hamilton circuits: Hamilton Circuit 1:
On Hamilton Decompositions
Dhananjay P. Mehendale Sir Paraቤተ መጻሕፍቲ ባይዱhurambhau College, Tilak Road, Pune-411030, India Abstract
P. J. Kelly conjectured in 1968 that every diregular tournament on (2n+1) points can be decomposed in directed Hamilton circuits [1]. We define so called leading diregular tournament on (2n+1) points and show that it can be decomposed in directed Hamilton circuits when (2n+1) is a prime number. When (2n+1) is not a prime number this method does not work and we will need to devise some another method. We also propose a general method to find Hamilton decomposition of certain tournament for all sizes. 1. Preliminaries: We begin with few definitions: Let G be a digraph with vertex set, V (G ) = {v1 , v2 ,L, vn } , and the set of directed edges, E (G ) , and let δ (vi ) and δ (vi ) be the in-degree and out-degree of vertex vi respectively. We associate an ordered pair ( mi , ni ) with each vertex vi and call it didegree of vi , representing respectively in-degree and out-degree of