本文仿照埃及金字塔的形状,设计了一类金字塔图,它包括平面金字塔图和立体多面金字塔图,并用一般图中构造哈密顿轨(圈)的自组织算法(S—O算法)研究了它们的哈密顿图性质。同时,也验证了S—O算法的有效性
doc.guandang.net
金字塔图的哈密顿图性质研究
宁安琪[1] 宁宣熙[2]
(南京航空航天大学经济与管理学院,南京,210016) [1]:ningangie@163.com [2]:nhning@nuaa,edu.cn
摘要:本文仿照埃及金字塔的形状,设计了一类金字塔图,它包括平面金字塔图和立体多面金字塔图,并用一般图中构造哈密顿轨(圈)的自组织算法(S—O算法)研究了它们的哈密顿图性质。同时,也验证了S—O算法的有效性。
关键词:哈密顿图,哈密顿轨(圈),多项式算法
Research on the Hamiltonicity of pyramid graphs
Angelika Ning and Xuanxi Ning
(College of Economic and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, P. R. China)
Abstract: Pyramid graphs are designed on the model of the pyramids in Egypt. They are divided in two types: plain and three-dimensional. The Hamiltonicity of this kind of graphs is studied by using the self-organization algorithm (S-0 algorithm) and concurrently the polynomial characteristic of the algorithm is also verified.
Key words: Hamiltonicity, Hamiltonian Graph, Hamiltonian circuit (path), Polynomial Algorithm
在一般图中构造哈密顿轨(圈)的算法研究
[1]-[4]
中,设计各种不同的哈密顿图去进行算
法的可行性及计算复杂性的研究是十分重要的环节。为此,我们已经设计过塔形图,套装图,四正则围城迷宫图,连环图等[3],它们都在验证一般图中构造哈密顿轨(圈)的自组织算法的有效性起了重要作用。在本文我们将仿照埃及金字塔的形状,设计了一类金字塔图,它包括平面金字塔图和立体多面金字塔图,并用S—O算法研究了他们的哈密顿图性质。
1, 平面金字塔图
所谓平面金字塔图是仿照埃及金字塔的单面外形设计的,并假设它由图1所示的砖块堆砌而成。图中各线的交点均为图的顶点。假设塔的层数为m层,尖顶为第0层,很显然,从第一层以后,每层的节点数呈增量为2的等差级数。其节点总数为:
n=(m 1)a+
Cn=8×5+
(m 1)(m 2)
d+(m+2)+1,式中a为首项,d为级差。
2
对于图1所示的平面金字塔图,a=5,m=9,所以
8×7
×2+11+1=108 2
国家自然科学基金资助项目(No79970003和No70571037)
扇面蜂巢图及其哈密顿图... 7页 免费 金字塔图的哈密顿图性质... 7页 ...研究了几种存在哈密顿圈的四正则连环图,并给出了一种构造其哈密顿圈的多项式算法...
引言 一个连通图中哈密顿回路的存在性和构造方法是图论中的一个重要问题[1];...金字塔图的哈密顿图性质研究〔 EB/OL 〕 . http://www.paper.edu.cn/...
金字塔图的哈密顿图性质研... 7页 免费 四正则连环图的哈密顿图性... 8...文中研究了这种扇面蜂巢图的哈密顿图性质,给出了这一类图的标准哈密顿圈的构造法...
本科图论-第十五章-欧拉图与哈密顿图 隐藏>> 2014-1-11 数理逻辑 离散数学 集合论 图 论 代数结构 图论研究图的逻辑 结构与性质,不关 注图的具体几何形 ...
哈密顿图 带权图与货郎担问题 1 15.1 欧拉图历史...他研究了这个 问题,并在一七三六年发表了《哥尼斯堡...()及简单图的性质,用反证法证明 连通 及简单图的...
8.1 8.2 8.3 二部图 欧拉图 哈密顿图_数学_自然科学_专业资料。山东...难点:平面图的性质与相关定理。 教学内容: 8.1 二部图 一、本节主要内容 ...
第十五章 欧拉图与哈密顿图主要内容 欧拉图 哈密顿图 带权图与货郎担问题 1 ...及简单图的性质,用反证法证明 连通 及简单图的性质, 连通. ? 及简单图的...
Hamilton 图的充分条件,必要条件,并根据 Hamilton 图的相关性质给出了若干 种...定义 2.4 设无 向图 G = V , E 是 哈密顿图 ,对于任 意 V1 ? V ...
解答 G1:1a2b3c4d5e1 G2:无哈密顿回路 哈密顿回路 是哈密顿图 不是哈密顿图 2.哈密顿图的性质: 2.哈密顿图的性质: 哈密顿图的性质 (1)设图G有n个点,...
地球物理研究所博士研究生 ,主要从事地震波成像和...2 动力学系统的哈密顿表述与辛性质 2. 1 哈密顿...3 Marmousi velocity model 图4 两种方法得到单炮...
热门文档