四角链的一些极值问题

来源 :厦门大学 | 被引量 : 0次 | 上传用户:mzhou2009
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在组合图论中有一个所谓的“细胞生长”问题,它与动物的发育很类似:从一个特定的正多边形(相当于一个细胞)开始,在平面上一步步向外“生长”,每生长一步即在其外围添加一个相同的细胞且至少有一条边完全重合。如果细胞是一个正方形,则称生成的动物为polyominoes。Polyominoes的研究拥有很悠久的历史,早在20世纪初人们就开始研究它,其中有关数学方面的研究主要集中在覆盖问题、非同构计数问题、匹配计数与排序问题等方面。迄今为止,人们在这些方面已经取得了很多成果。一个polyomino同时也是由方点阵中有限多个以边相连接的正方形的并所组成的一个平面几何图形。在统计物理学中,m×n阶方点阵和m×n阶六角点阵中独立集的计数分别被称为hard四角问题和hard六角问题。 本文我们考虑一类特殊的方点阵——四角链(polyominochain)关于k-匹配数和k-独立集数等参数的极值问题。设Tn表示所有含n个正方形的四角链的集合。对任意四角链Tn∈Tn,分别用mk(Tn)和ik(Tn)表示Tn的k-匹配数和k-独立集数。本文我们证明了对任意四角链Tn∈Tn和任意k≥0,mk(Ln)≥mk(Tn)≥mk(Zn),ik(Ln)≤ik(Tn)≤ik(Zn),且左边的等式对所有k成立当且仅当Tn=Ln,右边的等式对所有k成立当且仅当Tn=An,这里Ln和Zn分别表示线性四角链和锯齿四角链。最后我们分别给出四角链的Hosoya指标(即∑kmk(Tn))和Merrifield-Simmons指标(即∑kik(Tn))的上下界及其递推式。
其他文献
本文从机电设备安装常见的问题入手,探讨了问题的解决对策,对相关工作人员有一定的借鉴作用。
期刊
建筑工程预算与造价管理是为了更好地对建筑工程进行先期的整体性把握和控制,为建筑工程中其他工作环节的顺利进行提供保证。一个科学合理的建筑工程预算与造价管理机制是在建
期刊
建筑工程项目施工的现场管理需要项目的管理者根据工程的具体情况,采取合理、科学的管理措施和方法,在确保工程质量的前提下,提高企业的经济效益,从而保证企业能够长期、稳定、持
期刊
近些年,稀疏表示被成功地应用在很多领域,包括图像去噪、图像超分辨率、面部识别、以及更难的任务如图像分类、物体识别等领域。这主要是因为很多高维的自然信号近似地存在于
圆盘控制点Bézier/B样条曲线就是控制顶点为圆盘的曲线。类似地,在三维欧氏空间中,我们可以定义球域控制点Bézier/B样条曲面,这些曲面即为控制顶点为球域的曲面。上述的曲线和
本文主要研究三个问题,一是加性码的计数,二是ZpZp2加性码理论,三是基于码字的纠错能力的一些讨论。  首先解决的是加性码的计数问题,包括四个方面,即任意有限交换p群中任意类型