和图与整和图

《和图与整和图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ｘ７６４６７０单位代码１０４４５’学号０１１６０９分类号０１５７．６止荪街缸史学硕士学位论文论文题目学科专业名称申请人姓名和图与整和图应用数学黟韶Ｌ导师姓名熹７担玖教授论文提交时间２００５年４月１５日独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得（注：如没有其他需要特别声明的，本栏可空）或其他教育机构的学位或证书使用过的材料。与我～同工作的同志对本研

2、究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者虢彭祆撕粹翮极学位论文版权使用授权书本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保宦ｆ劳向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权—堂±ｔ可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩Ｅ¨或扫描等复刹手段保存、汇编学位论文。（保密的学位沦文在解密后适用本授权书）学位论文作者签名：岛狄导师签字：毒莎饭签字Ｆ１期：２００｝年缸月７五日签字Ｒ期：２００ｒ年牛月ｆ２日山东

3、师范大学坝士学位论文和圈与整和图彭敬（山东师范大学数学科学院，济南，山东，２５００１４）中文摘要从实用的观点来看，和图标号可用作图的压缩表示，即表示图的结构．当利用输入图的压缩表示来工作时，数据压缩不仅可以节省内存，还可以加快某些图算法的运算速度．和图的概念是Ｆ．Ｈａｒａｒｙｌ９９０年提出的．设Ｇ＝（矿（Ｇ），￡（Ｇ））是一个图，其中ｖ（Ｇ），Ｅ（Ｇ）分别表示Ｇ的顶点集和边集，简记为Ｖ和Ｅ．令Ⅳ（ｚ）表示正整数（整数）集～（Ｚ）的非空有限子集Ｓ的和图Ｇ’（Ｓ）是图（Ｓ，Ｅ），其中Ｕｖ∈Ｅ当且仅当“＋Ｖ∈Ｓ．

4、对于图Ｇ，若存在ＳｃⅣ（ｚ），使得Ｇ兰Ｇ＋（＿ｓ．），则称图Ｇ是（整）和图．对于任意图Ｇ若存在最小的非负整数盯＝盯（Ｇ）（ｆ＝ｆ（Ｇ））使得Ｇｕａ（ＯＫ。为（整）和图，称此数为Ｇ的（整）和数，即：Ｏ－＝ｏ－（Ｇ）＝ｍｉｎ｛ｓ：ｊＳｃＮ，使得ＧｕｓＫｌ兰Ｇ＋（Ｓ），其中Ｓ２０ｊ（ｆ＝ｆ（Ｇ）＝ｒａｉｎ｛ｓ：３ＳｃＺ，使得ＧｔｐｓＫｌ三Ｇ＋（Ｓ），其中ｓ≥Ｏ｝）．显然对任意的图Ｇ有ｆ（Ｇ）ｓ盯（Ｇ）．为了更好地理解和图与整和图的定义，许多作者又给出了ｆ整）和标号的定义：图Ｇ的一个标号是ｙ（Ｇ）。Ⅳ（Ｚ）的～一映

5、射Ｌ．如果存在图Ｇ的一个标号￡满足：对矿（Ｇ）。ｐ的任意两个互异顶点“和ｖ，“ｖＥ￡（Ｇ）当且仅当存在ｗ∈矿（Ｇ）使得１４ｕ）＋￡（Ｖ）＝Ｌ（ｕ，），则称此标号Ｌ为图Ｇ的一个（整）和标号．为了方便，在本文中，如果没有特殊说明，顶点的（整）和标号与顶点可以不加区分．自１９９０年Ｈａｒａｒｙ提出了和图的概念，开始了对和图的研究．目前对和图的研究主要是从一些特殊图类着手，确定它们的和数、整和数．迄今为止，已经知道一些简单图类的和数与整和数，如：完全图Ｋ。，ＮＣ一路只，二分图Ｋ～，轮吼，扇Ｆ．，酒会图ｉ瓦等．但是对

6、和图整和图性质的研究却不是很多山东师托大学硕士学位论文在本文的第一章，我们主要介绍了文章中所涉及的一些概念、术语和符号：在第二章中，我们讨论了整和图的性质；在第三章中，分别确定了图Ⅳ。一Ｅ（ｎＫ：）与图Ｇ…的和数，定义了新图只。、￡。并给出了和数的上、下界，定义了一类新的不可兼图ｃ…：在第四章中，利用粘合的方法证明了又点距离至少为２且每个叉点上有一个距离为２的路的树为整和图．在本文中，主要得到以下定理：定理２．１拧阶（”≥４）整和图Ｇ至多有两个ＩＩ—ｌ度顶点：Ｇ含两个”～ｌ度顶点当且仅当Ｇ兰Ｇ＋（一ｌ，０，

7、ｌ，２，…，ｒｔ一２）．定理２、２设Ｇ为一个＂阶（仃≥４）图，有以下结论：（１）若６（Ｇ）≥ｆ爿＋１，则Ｇ不是整和图：且界不可以改进（２）令盯！垒ｍｊｎ｛ｓ＋ｓ＇：ｓ≠ｓ＇ｅＳ，ｓｓ＇甚Ｅ｝，若盯：≥２ｆ兰１＋２，则Ｇ不是整和图：且界不可以改进定理２．３设Ｇ是一个”阶（＂≥４）图，如果△（Ｇ）蔓ｒｔ一２，那么有以下结论（１）若艿（Ｇ）≥ｌ兰ｊ＋ｌ，则Ｇ不是整和图：．且界不可以改进他’若口！≥２ｌ兰ｊ＋２，则Ｇ不是整和图定理３．１．１对＂≥５，ｃｒ（Ｋ。，一Ｅ（ｎＫ２）＝２，，一３定理３．２．１对＂２３，ｃｒ

8、（Ｇ。。）＝２＂＋１定理３．３．２２ｎ≤ｃｒ（Ｐｏｊ）ｓ２ｎ＋２山东师范大学硕士学位论立定理３．４．３ｎ≥３时，２蔓仃（ｔ）≤３．定理３．５对ｎ≥５，Ｃ。是不可兼图定理４．２叉点距离至少为２且每个叉点上有～个距离为２的路的树为整和图关键词（整）和图；（整）和数：（整）和标号分类号０１５７．６山东师范大学硕士学位葩文ＴｈｅＳＵｍｇｒａｐｈａｎｄｔｈｅｉｎｔｅｇｒａｌｓｕｍｇｒａｐｈＪｉｎｇＰｅｎｇＳｈ