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

本书特色

[

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

]

内容简介

[

本书主要内容包括: 图的基本概念, l1-空间, 超立方图, 图的等距离嵌入, l1-嵌入, 可平面图的l1-嵌入, 团和运算下的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-识别参考文献后记

封面

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

作者:王广富著

页数:160页

定价:¥49.8

出版社:东南大学出版社

出版日期:2017-12-01

ISBN:9787564175719

PDF电子书大小:46MB 高清扫描完整版