| 若干曲面多边形图的l1-嵌入 |
| Alternative Title | l1-embeddability of some polygonal graphs on surfaces
|
| 王广富 |
| Thesis Advisor | 张和平
|
| 2010-05-26
|
| Degree Grantor | 兰州大学
|
| Place of Conferral | 兰州
|
| Degree Name | 博士
|
| Keyword | 超立方图
$\lambda$-嵌入
$l_1$-图
$l_1$-嵌入
等距离子图
凸子图
|
| Abstract | 连通图~$G=(V,E)$~的两个顶点~$u$~和~$v$~之间的距离~$d_{G}(u,v)$~定义为~$G$~中连接~$u$~和~$v$~的最短路的长度.
则~$d_G$~是~$V(G)$~上的一个度量, $(V(G),d_G)$~为~$G$~的伴随度量空间.
一个图~$G=(V,E)$~称为~$l_1$-图~(也称为~$l_1$-嵌入的),
如果存在正整数~$m$,
使得它的伴随度量空间~($V,d_G$)~可以等距离地嵌入到~$l_1$-空间~$(\mathbb{R}^m, d_{l_1})$~中. 即存在从~$V(G)$~到~$\mathbb{R}^m$~的一 个映射~$\phi$~使得对图~$G$~
的任意两个顶点~$x,y$~都有~$d_G(x, y)= d_{l_1}(\phi(x),\phi(y))$~
成立.
本文主要研究了开口纳米管在超立方图中的嵌入,
两类规则的牟比乌斯带上的六边形堆砌图的~$l_1$-嵌入, 在粘边运算下
图的~$l_1$-嵌入, 和牟比乌斯带上的四边形堆砌图的~$l_1$-嵌入.
全文共分为五章, 第一章首先介绍了~$l_1$-空间的基本概念, 其次介绍了
~$l_1$-图的基本理论以及相关问题的研究进展, 再次介绍了特殊的
~$l_1$-嵌入----等距离嵌入的一些理论.
本章最后罗列了本文得到的主要结果.
在第二章中, 我们研究了开口纳米管在超立方图中的嵌入.
我们证明了在所有的开口纳米管中只有三类特殊的纳米管, 即~$(0,1)$-型,
$(1,0)$-型和~$(1,1)$-型的纳米管是可以等距离嵌入到超立方图中的.
在第三章中, 对两类规则的牟比乌斯带上的六边形堆砌图~$H_{2m,2k}$~和
~$H_{2m+1,2k+1}$, 利用边的~ $l_1$-标号和~ $l_1$-图的识别算法,
我们证明了只有~ $H_{2,2}$~ 和~ $H_{3,3}$~ 是~ $l_1$-嵌入的.
在第四章中, 我们讨论了由两个 ~$l_1$-图通过粘贴一条边所得到的新图的
~$l_1$-嵌入性. 我们证明了当至少有一个是二部图时, 两个
~$l_1$-图通过粘贴一条边得到的新图仍是 ~$l_1$-图.
最后我们给出两个例子说明两个非二部的~
$l_1$-图通过粘贴一条边所得到的新图可能是一个~$l_1$-图, 也可能不是
一个~$l_1$-图.
在第五章中, 我们主要研究了牟比乌斯带上的四边形堆砌图的~$l_1$-嵌入性.
我们考查了牟比乌斯带和闭圆盘上的四边形堆砌图的平衡数,
得到牟比乌斯带和闭圆盘上的四边形堆砌图的平衡数分别是~0~和~4.
其次我们讨论了围长为~ 3~的~$l_1$-嵌入的牟比乌斯带上的四边形堆砌图,
并得到了其中的两个禁止子图.
对于围长为~4~的~$l_1$-嵌入的牟比乌斯带上的四边形堆砌图,
我们证明了其最短的非零伦圈是等距离圈~(也是凸的)~且是唯一的; 进一步,
沿着这个最短的非零伦圈``剪开"后所得到的新图的每个分支都是一个平面方格图.
最后我们构造了无穷多个围长为~4~的~$l_1$-嵌入的牟比乌斯带上的四边形堆砌图. |
| Other Abstract | The distance $d_G(u,v)$ between two vertices $u$ and $v$ of a
connected graph $G=(V,E)$ is defined as the length of a shortest path connecting them in $G$. So $d_G$ is a metric on $V(G)$, and
$(V(G),d_G)$ is a graphic metric space associated with $G$.
A graph $G=(V,E)$ is called an $l_1$-graph (sometimes called
$l_1$-embeddable),if there exists a positive integer $m$,such that
its graphic metric space $(V, d_G)$ can be isometrically embedded
into the $l_1$-space $(\mathbb{R}^m, d_{l_1})$,that is,there
exists a mapping $\phi$ from $V(G)$ onto $\mathbb{R}^m$ such that
$d_G(x, y)= d_{l_1}(\phi(x),\phi(y))$ for any two vertices $x,y$ of
$G$.
In this thesis, we consider the embeddability of open-ended
nanotubes into hypercubes, $l_1$-embeddability of two classes of
regular M\"{o}bius hexagonal tiling graphs, the $l_1$-embeddability
of graphs under edge-gluing operation, and the $l_1$-embeddability
of M\"{o}bius quadrilateral tiling graphs.
This
thesis consists of five chapters. In Chapter one, firstly we
introduce the background of the $l_1$-space; secondly, we introduce
the basic theory of $l_1$-graphs and the correlative research
problems and their developments; thirdly, we introduce some theory
of a special $l_1$-embedding----isometric embedding; finally, we
present the main results obtained in the following chapters.
In Chapter two, we study the embeddability of open-ended nanotubes
into hypercube. Among all the open-ended nanotubes only three
classes of special nanotubes, i.e., $(0,1)$-type, $(1,0)$-type and
$(1,1)$-type nanotubes can be isometrically embedded into
hypercubes.
In Chapter three, for the two classes of regular M\"{o}bius
hexagonal tiling graphs $H_{2m,2k}$ and $H_{2m+1,2k+1}$, by using
$l_1$-labels of edges and the recognition algorithm of $l_1$-graphs,
we obtain that only $H_{2,2}$ and $H_{3,3}$ are $l_1$-embeddalbe.
In Chapter four, we discuss the $l_1$-embeddability of graphs
obtained from two $l_1$-graphs by gluing an edge. Firstly, we prove
that if at least one of the two graphs is bipartite, then the new
graph obtained from them by gluing an edge is also an $l_1$-graph.
Then, we give two examples to show that for two nonbipartite
$l_1$-graphs, the new graph obtained from them by gluing an edge
may be an $l_1$-graph or may not be an $l_1$-graph.
In Chapter five, we mainly study the $l_1$-embeddability of
M\"{o}bius quadrilateral tiling graphs. First of all, we investigate
the balance number of quadrilateral tiling graphs on t... |
| URL | 查看原文
|
| Language | 中文
|
| Document Type | 学位论文
|
| Identifier | https://ir.lzu.edu.cn/handle/262010/224766
|
| Collection | 数学与统计学院
|
Recommended Citation
GB/T 7714 |
王广富. 若干曲面多边形图的l1-嵌入[D]. 兰州. 兰州大学,2010.
|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
