图的l1-嵌入性以及partial立方图和多重median图的刻画

Metric is a basic concept in analysis and it is in the core of the research in graph theory, combinatorial optimization and more generally, discrete mathematics. Embeddings of metric space have extensive applications such as in operational research, electric net, theoretical chemistry, computer science and biologies. A graph G is called an l1-graph(or l1-embeddable), if the graphic metric space associated with G can be isometrically embedded into the l1-space. This project will mainly study the following problems: the l1-embeddability of the new graph under gated amalgamations; according to the l1-embeddability, complete the classifications of the quidrilateral and hexagonal tiling graphs embedded in Mobius strip as well as the projective plane Fullerenes; explore the equivalent conditions for partial cubes and characterize regular partial cubes; study the basic properties and structure of the multimedian graphs. This study aims to further enrich and develop the l1-embeddable theories of graphs and provides important theoretical basis for computer networks and chemical graph theory.

度量是分析学中的基本概念, 同时也是图论、组合优化等离散数学中比较核心的研究对象． 度量空间的嵌入在运筹学, 电网络, 理论化学, 计算机科学以及生物学等方面均有广泛应用. 如果图G的伴随度量空间能等距离地嵌入到l1-空间, 则称该图为l1-图(或l1-嵌入的). 本项目将探索两个l1-图作门合并运算后所得新图的l1-嵌入性; 利用 l1-嵌入性对莫比乌斯带上的四边形和六边形堆砌图以及射影平面富勒烯进行分类; 给出二部的l1-图即partial立方图的等价刻画条件, 并分析正则的partial立方图的特性; 研究多重median图的基本性质及结构．本研究将 进一步丰富和发展图的l1-嵌入性理论，并为计算机网络和化学图论提供重要的理论依据.

度量(距离)是图论、组合优化等离散数学中非常核心的研究对象。它在其他数学领域及应用也都出现过，比如距离几何、设计理论、分析和概率论等. 除了数学理论上的研究,度量还在其他领域有很多应用。在计算机科学中, 最近邻点搜索， 点集直径的计算以及网络搜索等都属于这个范畴. 在生物学中, 许多计算基因组学的应用需要DNA或蛋白质序列的数据库的搜索或聚类。为了解决此类问题， 人们通常是利用问题对象所处的空间来获得更好的算法。很遗憾的是，很多有意义的度量空间尚未被深入研究，因而其中很多有用的结构定理尚不为人所知。受此问题的驱动, 一个自然的想法是将考虑的问题对象放到一些研究很成熟的基本度量空间中，然后利用基本度量空间的特殊结构性质来获得更有效的算法。本项目主要研究图度量空间在l_1-空间中的等距离嵌入的问题。 .本项目的主要研究内容和结果: 1. 探索两个l_1-图作门合并运算后所得新图的l_1-嵌入性，发现至少有一个是二部图时，两个l_1-图作粘边运算后所得新图仍然是l_1-图；两个l_1-图作门合并运算后所得新图仍然是l_1-图。2. 研究莫比乌斯带上的四边形堆砌图和六边形堆砌图以及射影平面富勒烯的 l_1-嵌入性, 我们刻画出了l_1-嵌入的莫比乌斯带上的四边形堆砌图的结构特性，它有唯一的一个最短非零伦圈；沿此圈割开后， 每个分支都是平面四边形堆砌图；将分支视为顶点，两个分支共享圈的一部分连一条边，则分支图是带有（也可能没有）若干悬挂点的圈；发现著名的Petersen图l_1-嵌入的射影平面富勒烯图。3. 探索正则的partial立方图的等价刻画条件, 对一个二元字符串f，我们证明了广义斐波那契立方Q_d (f)是partial立方图当且仅当广义斐波那契立方Q_d (f^n)是partial立方图。4. 研究多重 median图的基本性质. 提出了多重median图的概念， 经研究发现多重median图都是二部图; 多重median图的收缩图以及两个多重median图的积图仍是多重median图; 两个多重median图粘点或者粘边之后所得新图仍是多重median图; 除了median图之外的多重median图都不是partial立方图; 多重median图的区间导出子图仍是多重median图。