| 【中文题名】 | 带宽临界图与带宽极图问题 |
| 【英文题名】 | |
| 【学科专业】 | 计算数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2002-1-14 |
| 【中关键词】 | 图,标号,带宽,k-临界,极图．, |
| 【英关键词】 | graph, labeling, bandwidth, k-critical, extremal graph., |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
带宽是图论中的一个重要的不变量。其定义如下。给定一个简单图
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-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 |
|
| 【DOI】 | LunWen.ID:2.2008.11325 |
