图的l1-嵌入性理论及其应用

　　现实世界中，许多问题都可以用图来表示。这里的“图”是指由点和线构成的图形，例如，点代表车站，线代表铁路构成的铁路网络图；点代表计算机，线代表连接计算机的网线构成的计算机网络图；点代表电子元件，线代表电子元件之间连接的物理导线构成的电网络图等，事实上，对给定的对象集合，对象间定义一种二元关系，两个对象之间具有此二元关系，则连接一条线，否则不连线，这就构成了一个图，图论正是研究这类图的结构和性质等问题的一门学科。自1736年Euler发表*篇图论论文——《哥尼斯堡的七座桥》开始，特别是20世纪70年代随着计算机科学的发展，图论发展十分迅速，应用也十分广泛。它在物理学、化学、运筹学、计算机科学、网络理论等方面均有应用。度量（或距离）空间是泛函分析中基本的概念，它为统一处理分析学各分支的重要问题提供了一个共同基础，它研究的范围非常广泛，包括了在工程技术、物理学和数学中遇到的许多有用的函数空间。同时，度量（或距离）也是图论、组合优化等离散数学中非常核心的研究对象，比如两点之间的短路问题、中国邮递员问题、网络大流等问题。它在其他数学领域及应用中也都出现过，比如距离几何（distancegeometry），组合矩阵论、设计理论、量子力学、统计物理、分析和概率论等。除了数学理论上的研究，度量还在其他领域有很多应用。在计算机科学中，许多基本的问题都涉及数据点集以及它们之间的相似性或异样。数据分类、*近邻点搜索、点集直径的计算以及网络搜索等都属于这个范畴，在生物学中，许多计算基因组学的应用需要DNA或蛋白质序列的数据库的搜索或聚类，为了解决此类问题，人们通常是利用问题对象所处的空间来获得更好的算法。但遗憾的是，很多有意义的度量空间尚未被深入研究，因而其中很多有用的结构定理尚不为人所知。受此问题的驱动，一个自然的想法是将考虑的问题对象放到一些研究很成熟的基本度量空间中，然后利用基本度量空间的特殊结构性质来获得更有效的算法。例如图的Wiener指标，即图中所有点对之间的距离和，直接利用定义公式计算，其复杂度为顶点立方阶的。但若图是l1-嵌入的，其计算复杂度则可以降为顶点线性阶的。因此研究图的伴随度量空间能否等距离嵌入到l1-空间中，具有重要的意义。

暂缺《图的l1-嵌入性理论及其应用》作者简介

第1章 图的基本概念
1．1 图与子图
1．2 同构和自同构
1．3 途径、路和圈
1．4 距离和区间
1．5 图的运算
1．6 常见图类
第2章 l1-空间
2．1 l1-空间
2．2 l1-嵌入的条件
第3章 超立方图
3．1 超立方图的定义
3．2 超立方图的自同构群
3．3 超立方图的度量结构
3．4 超立方图的刻画
3．5 区间距离单调图
第4章 图的等距离嵌入
4．1 关系θ的定义和基本性质
4．2 图在卡式积图中的等距离嵌入
4．3 部分立方图的刻画
4．4 median图
第5章 l1-嵌入
5．1 引言
5．2 定义和初步的结果
5．3 原子图
5．4 l1-图的标号
第6章 可平面图的l1-嵌入
6．1 半立方图的等距离子图
6．2 平面图的交错割
6．3 l1-图的Wiener指标
第7章 团和运算下的l1-嵌入
7．1 团1-和运算
7．2 团2-和运算
第8章 化学分子图的l1-嵌入
8．1 苯图的嵌入
8．2 冠状苯系统的l1-嵌入
8．3 开口纳米管的l1-嵌入
第9章 规则的莫比乌斯带上的六边形和四边形堆砌图的Z．-嵌入
9．1 规则的莫比乌斯带上的六边形堆砌图的l1一嵌入
9．2 规则的莫比乌斯带上的四边形堆砌图的l1-嵌入
第10章 莫比乌斯带上的四边形地图的l1-嵌入
10．1 引言
10．2 四边形地图
10．3 l1-图的边标号
10．4 短的非零伦圈
10．5 分支图
10．6 一类l1-嵌入的莫比乌斯带上的四边形地图
10．7 GAP软件和图的l1-识别
参考文献
后记