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

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

    参考文献
    后记
  • 内容简介:
      现实世界中,许多问题都可以用图来表示。这里的“图”是指由点和线构成的图形,例如,点代表车站,线代表铁路构成的铁路网络图;点代表计算机,线代表连接计算机的网线构成的计算机网络图;点代表电子元件,线代表电子元件之间连接的物理导线构成的电网络图等,事实上,对给定的对象集合,对象间定义一种二元关系,两个对象之间具有此二元关系,则连接一条线,否则不连线,这就构成了一个图,图论正是研究这类图的结构和性质等问题的一门学科。
      自1736年Euler发表第一篇图论论文——《哥尼斯堡的七座桥》开始,特别是20世纪70年代随着计算机科学的发展,图论发展十分迅速,应用也十分广泛。它在物理学、化学、运筹学、计算机科学、网络理论等方面均有应用。
      度量(或距离)空间是泛函分析中基本的概念,它为统一处理分析学各分支的重要问题提供了一个共同基础,它研究的范围非常广泛,包括了在工程技术、物理学和数学中遇到的许多有用的函数空间。同时,度量(或距离)也是图论、组合优化等离散数学中非常核心的研究对象,比如两点之间的短路问题、中国邮递员问题、网络大流等问题。它在其他数学领域及应用中也都出现过,比如距离几何(distancegeometry),组合矩阵论、设计理论、量子力学、统计物理、分析和概率论等。
      除了数学理论上的研究,度量还在其他领域有很多应用。在计算机科学中,许多基本的问题都涉及数据点集以及它们之间的相似性或异样。数据分类、最近邻点搜索、点集直径的计算以及网络搜索等都属于这个范畴,在生物学中,许多计算基因组学的应用需要DNA或蛋白质序列的数据库的搜索或聚类,为了解决此类问题,人们通常是利用问题对象所处的空间来获得更好的算法。但遗憾的是,很多有意义的度量空间尚未被深入研究,因而其中很多有用的结构定理尚不为人所知。受此问题的驱动,一个自然的想法是将考虑的问题对象放到一些研究很成熟的基本度量空间中,然后利用基本度量空间的特殊结构性质来获得更有效的算法。例如图的Wiener指标,即图中所有点对之间的距离和,直接利用定义公式计算,其复杂度为顶点立方阶的。但若图是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-嵌入性理论及其应用
图的控制参数
徐保根
图的l1-嵌入性理论及其应用
图的匹配多项式及其应用
马海成 著
图的l1-嵌入性理论及其应用
图的有限制条件染色引论(英)
蔡建生、王纪辉、张霞 编
图的l1-嵌入性理论及其应用
图的特征值/同济博士论丛
邵嘉裕 著;袁西英、伍江、雷星晖 编
图的l1-嵌入性理论及其应用
图的彩虹连通数(英文版)
董九英
图的l1-嵌入性理论及其应用
图的哈密尔顿性与连通性的谱刻画
余桂东 著
图的l1-嵌入性理论及其应用
图的度因子和分支因子(英文)
周思中 著
图的l1-嵌入性理论及其应用
图的彩虹连通性与零和问题(英文)
刘素娟、王林林 著
图的l1-嵌入性理论及其应用
图的多叶距粒度正则子树结构研究
杨雨
图的l1-嵌入性理论及其应用
图的特征值与连通性研究
洪振木 著
图的l1-嵌入性理论及其应用
图的Estrada指数与具有极大P-点个数的树矩阵/同济博士论丛
邵嘉裕 著;杜志斌、伍江、雷星晖 编
图的l1-嵌入性理论及其应用
图的着色问题研究
张桂芝、黄月梅、安永红 著
系列丛书 / 更多
图的l1-嵌入性理论及其应用
图的控制参数
徐保根
图的l1-嵌入性理论及其应用
图的匹配多项式及其应用
马海成 著
图的l1-嵌入性理论及其应用
图的有限制条件染色引论(英)
蔡建生、王纪辉、张霞 编
图的l1-嵌入性理论及其应用
图的特征值/同济博士论丛
邵嘉裕 著;袁西英、伍江、雷星晖 编
图的l1-嵌入性理论及其应用
图的彩虹连通数(英文版)
董九英
图的l1-嵌入性理论及其应用
图的哈密尔顿性与连通性的谱刻画
余桂东 著
图的l1-嵌入性理论及其应用
图的度因子和分支因子(英文)
周思中 著
图的l1-嵌入性理论及其应用
图的彩虹连通性与零和问题(英文)
刘素娟、王林林 著
图的l1-嵌入性理论及其应用
图的多叶距粒度正则子树结构研究
杨雨
图的l1-嵌入性理论及其应用
图的特征值与连通性研究
洪振木 著
图的l1-嵌入性理论及其应用
图的Estrada指数与具有极大P-点个数的树矩阵/同济博士论丛
邵嘉裕 著;杜志斌、伍江、雷星晖 编
图的l1-嵌入性理论及其应用
图的着色问题研究
张桂芝、黄月梅、安永红 著
相关图书 / 更多
图的l1-嵌入性理论及其应用
图的控制参数
徐保根
图的l1-嵌入性理论及其应用
图的匹配多项式及其应用
马海成 著
图的l1-嵌入性理论及其应用
图的有限制条件染色引论(英)
蔡建生、王纪辉、张霞 编
图的l1-嵌入性理论及其应用
图的特征值/同济博士论丛
邵嘉裕 著;袁西英、伍江、雷星晖 编
图的l1-嵌入性理论及其应用
图的彩虹连通数(英文版)
董九英
图的l1-嵌入性理论及其应用
图的哈密尔顿性与连通性的谱刻画
余桂东 著
图的l1-嵌入性理论及其应用
图的度因子和分支因子(英文)
周思中 著
图的l1-嵌入性理论及其应用
图的彩虹连通性与零和问题(英文)
刘素娟、王林林 著
图的l1-嵌入性理论及其应用
图的多叶距粒度正则子树结构研究
杨雨
图的l1-嵌入性理论及其应用
图的特征值与连通性研究
洪振木 著
图的l1-嵌入性理论及其应用
图的Estrada指数与具有极大P-点个数的树矩阵/同济博士论丛
邵嘉裕 著;杜志斌、伍江、雷星晖 编
图的l1-嵌入性理论及其应用
图的着色问题研究
张桂芝、黄月梅、安永红 著