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

带宽临界图与带宽极图问题

作　者: 杨爱峰
导　师: 原晋江
学　校: 郑州大学
专　业: 计算数学
关键词: 图标号带宽 k-临界极图．
分类号: O157.5
类　型: 硕士论文
年　份: 2001年
下　载: 28次
引　用: 0次
阅　读: 论文下载

内容摘要

带宽是图论中的一个重要的不变量。其定义如下。给定一个简单图G=（V，E），其中|V|=p。任意一个双射f：V→｛1,2,…,p｝称为图G的一个标号。对图G的标号f，所有边两端的最大标号差B（G，f）=max|f（u）－f（v）|称为图G在标号f下的带宽；而B（G）=min｛B（G，f）：f是图G的标号｝是图G的带宽。本文研究了与图带宽的临界性和极值性有关的一些问题，由以下两部分组成：1．3-临界单圈图和3-临界树的刻划；2．带宽极图问题。1.3-临界单圈图和3-临界树的刻划。 Syslo和Zak首先提出了（带宽）k-临界图的概念（若B（G）=k，而图G的任意真子图的带宽小于k，就称图G是k-临界的）。P.Z.Chinn提出了另一种k-临界图的定义，即图G的带宽为k，但G经过删去任何一个顶点或收缩任何一个2度顶点这两种运算后所得到的图的带宽小于k，并且刻划了3-临界树的结构特征。本文采用第一种定义。我们在第二章里大致介绍了一般k-临界图的性质，给出了一系列3-临界单圈图，我们还刻划了3-临界树的部分结构特征，并且构造了许多3-临界树。定理1 设图G是圈C_n（n≥8）在点v₁及v_k处分别加悬挂边v₁x和v_ky（3≤k≤[n/2]-1），那么图G是3-临界的。定理2 设图G是圈Cn（n≥5且为奇数）在点v₁及v_k处分别加悬挂边v₁x,v₁y和v_kz（k=（n-1）/2），那么图G是一个3-临界的。定理3 设图G为圈Cn（n≥6且为偶数）在点v₁及v_k处加悬挂边v₁x,v₁y,v_kz和v_kt（k=n/2），那么图G是3-临界的。定理4 设图G为圈Cn（n≥5）在点v₁及v₂处加悬挂边v₁x,v₁y和v₂z，那么图G是3-临界的。另外，我们还给出了几个具体的3-临界单圈图，此处不再列出。定理5 对任意3－临界树丁p厂枉4X有 D（T）＋6 SI厂（丁川5 ZD（T）＋二．定理6 我们用以下方法构造的树T是3爿墒界的：门）在星局，3的三条边W3I砌ty及vov3上分别加I，b，el个剖分点，其中 15a5b： o)在（1）所得树的悬挂点川和心处分别联两个1度顶点，13处联一个1 度顶点，所得的树记为T 定理7 我们用以下方法构造的树TR3－临界的：＊)在星K；，。的三条边上分别加a人b个剖分点，其中卜 ash；（2）在（l）所得树的悬挂点上分别联两个1度顶点，所得的树记为T． 2．带宽极图问题文p尸1提出了一类极图问题：给定连通图 G的顶点数 p及带宽 B，求边数的最小值及相应的极图．本文受到此问题的启发，提出了另一类极图问题，图G除了满足上述条件以外，还要求d（QSB．这个边数的最小值就用函数M，B）表示．M，B)的极图是满足条件1叮G)l＝p，B（G）咄，6（G） sB 及【E（G【＝＝M，B）的图．我们在第三章里，给出了一些满足一定条件的加，B) 的表达式及相应的极图．命题二 O)当po时，M，1卜1，兄是加，n的唯一的极图：o)当尸打时，彻、Zto，C是穴A2)的唯的图：（3 o。＊一，兄是n 2 一1）的唯一的极图．定理8 设尸＝3灯r（kZ1，1三r三3）．则＊)当，；时，M，。一2卜七卜＋2，完全（k＋l“部图K3入，u。肋，。 tZ］“—、·——。，——一—、－．一2）的一个极图； O)当一Z时，加，p—2户叫尸卜r＋l，完全（k小部图K3人．V聊，n一门1 2）的一个极图； 5 ＊)当，3时，j（，。－2广0－A完全（k＋＊－部图K3，工，。幼，。－2）的 IZ）“”””’“”’“—“”“一个极图．定理 9 当尸 z 4B—2 （ z 3）时，s，B)＝r—l，Tr。幼F)的一个极图（图C的定义见第三章）．定理10 卜＋2 p＝4 。。、P＋lp＝5，6，7，8 o．3)＝｛“ IP P＝9 t P—lp Z 10 定理＊而．4；＝J P＋5。＝5 卜十3 尸＝6，7

全文目录

英文摘要  3-6
中文摘要  6-9
第一章引论  9-14
  1-1 带宽的应用背景  9-11
  1-2 带宽的主要研究课题  11-12
  1-3 带宽临界图及带宽极图问题的已知结果  12-14
第二章带宽临界图  14-24
  2-1 带宽k-临界图  14-15
  2-2 3-临界单圈图  15-18
  2-3 3-临界树  18-24
第三章带宽极图问题  24-32
  3-1 准备知识  24-26
  3-2 主要结果  26-32
参考文献  32-35
附录：本文常用术语记号  35-36
致谢  36

带宽临界图与带宽极图问题

内容摘要

全文目录

相似论文