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

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