学位论文 > 优秀研究生学位论文题录展示

图与超图的带宽和问题

作　者: 黄丹君
导　师: 卜月华
学　校: 浙江师范大学
专　业: 应用数学
关键词: 超图标号带宽和边标号边带宽和
分类号: O157.5
类　型: 硕士论文
年　份: 2004年
下　载: 80次
引　用: 0次
阅　读: 论文下载

内容摘要

超图带宽和问题是一个有许多应用背景的课题，其定义如下。给定一个有限集X上的超图H=（E₁，E₂，…，E_m），其中|X|=n。任意一个双射f：X→{1，2，…n}称为超图H的一个标号。对超图H的一个标号f及H的任一条边E，定义函数f（E）=max{|f（u）-f（v）||u，v∈E}，称为超图H的关于标号f的带宽和，称是超图H的标号}为超图H的带宽和，并称使BS（H）达到最小的标号f为超图H的一个最优标号。本文研究了超图带宽和问题中的一些问题，由以下三部分组成： 1．超图带宽和与图带宽和的关系注意到图带宽和问题是超图带宽和问题的特殊情形，但超图带宽和问题是否可以转化为图带宽和问题来考虑呢?本学位论文就考虑这个问题。在第二章里给出超图H的一个运算：将超图的每条边都用一条路代替，记所得的多重图类为g。超图带宽和问题可以根据所对应的多重图类中的某个图的带宽和问题来确定，由此还可以得到一些超图带宽和问题的下界。定理1 对于一个超图H=（E₁，E₂，…，E_m），（?）为如上定义的多重图类。则BS（H）=min{Bs（G）|G∈（?）}。定理2 对任一个线性超图H，都有BS（H）≤BS（[H]₂），等号成立当且仅当H为简单图。定理3 设H^*为线性超图H的对偶超图，L（H）为超图H的线图，△为超图H的最大度，则BS（H^*）≤BS（L（H）），等号成立当且仅当△=2。定理4 对于n阶线性超图H=（E₁，E₂，…，E_m），有定理5对于。阶线性超图H二（El，场，…，Etn），有，几 Bs（H*）全帆m，艺l尽I一川. ‘=12，图带宽和与其对偶超图带宽和的关系为讨论方便起见，在第三章里引进边带宽和的概念.给定一个有限集x上的超图H二（El，场，…，凡），其中}引=。.任意一个双射g:H一{l，2，…。}称为超图H的一个边标号.对超图H的一个边标号g及H的任一个点二，定义函数抓H（x）)=。ax{l0（尽）一抓马川尽，场〔H闰}，称Bs，（H，刃二艺或H（x））为超图H的关于边标号g的边带宽忿任X和，称BS’（H）一僧n{B夕（H，0）I。是超图H的边标号}为超图H的边带宽和，并称使Bsl(川达到最小的边标号g为超图H的一个最优边标号.定理6设超图H*二（x1，几，…，瓜）是超图H=（E;，场，…，‘）的对偶超图，则Bs（H*）=BS，(川. 对一般图G，BS（G）与Bs（G*）的大小关系是不确定的.但当G是森林或单圈图时，我们有下述结果.定理7设T是森林，则BS（T*）三BS(劝。定理8设G是一个单圈图，则BS（G*）三BS（G）.3.超图带宽和的某些下界由于超图带宽和间题是NP一完全的，于是人们通过以下两种途径扩充其结果:1、寻求超图带宽和问题的近似算法或启发式算法;2、求BS(川的上下界来确定某些特殊超图的带宽和.在第四章里利用超图H的度序列给出Bs(川的一个下界并建立了带宽和问题的HarPer型下界估计式，由此得到一系列特殊超图的带宽和.定理9设序列（al，由，…，心）是:一致超图H的度序列（r 22），。为超图H的边数.令。*一m二{}{EoH:E:s}}}“。X，lsl一好，则BS（H）Zm故{艺【艺成一（。p+。。）}，艺【艺d‘一r知』/（r一p=1云=1定理10材枷。。梯峡=（认召）是指:顶点集为v={。1，。2，…，。2*}，边集为刀={（。‘，朽）}l‘一jl=*，1，2、一1}，则刀s（从）=9无一5.定理11对任意。阶简单超图H，有BS（H）全艺mink=1}S}二k}{S，司}.定理12设H气x）是顶点x的:一致口- f（△“+l），（r一;）。s（二。（·））一}。，（△口幸2）（一）’ 气4星，△口是其最大尽度，则:当△乡为奇数时，当△口为偶数时.

全文目录

中文摘要  3-6
英文摘要  6-10
一、引论  10-16
  (一) 、超图带宽和问题的应用背景  10-12
  (二) 、研究现状  12-13
  (三) 、基本概念及符号  13-16
二、超图带宽和与图带宽和的关系  16-22
  (一) 、基本性质  16-18
  (二) 、超图带宽和与图带宽和的关系  18-20
  (三) 、超图带宽和问题的一些下界  20-22
三、图及其对偶超图带宽和的关系  22-32
  (一) 、超图的边带宽和  22-23
  (二) 、树及其对偶超图带宽和的关系  23-28
  (三) 、单圈图及其对偶超图带宽和的关系  28-32
四、超图带宽和问题的一些下界  32-41
  (一) 、超图带宽和问题的度序列方法  32-36
  (二) 、超图带宽和问题的Harper型下界  36-41
参考文献  41-43
致谢  43-44
攻读学位期间发表的学术论文目录  44

相似论文

关于几类图的分数色数,O157.5
基于GIS_GPS的武警作战指挥系统关键技术研究与实现,E211
基于可扩展哈希算法的并行爬虫动态负载均衡实现,TP391.3
城市突发公共事件伤员救治出救点选择与车辆路径集成优化研究,X928.04;U116.2
循环圈算术标号的研究,O157.5
关于路、圈并图优美性的研究,O157.5
关于DNA图及其标号图的研究,O157.5
A（m，n）图的顶点优美标号及超顶点优美标号的研究,O157.5
两类毛毛虫的多级距离数,O157.5
机器学习理论研究及其在车载导航系统中的应用,TN966
图的{P_r}-自由着色,O157.5
完全二部图K_（n，n）的循环圈分解及边—平衡指数集,O157.5
树状图的路覆盖问题及其应用,O157.5
基于场景和属性的需求引出及形式化建模,TP311.52
K_（4-e）链的边—平衡指数集,O157.5
图的（p，1）-全标号及图的弱邻点可区分的染色问题,O157.5
低标号砂浆空斗墙砌体的抗震性能及其加固关键问题研究,TU746.3
基于不动点理论的遗传算法研究,TP18
概率方法在超图二染色问题中的应用,O157.5
邻点可区分的染色和两种特殊的全染色问题,O157.5
带有邻域限制的三类染色问题,O157.5