图的空间理论:与图有关的线性代数理论(下)

对图的空间理论(尤其是圈空间)进行了总结:介绍了目前在这个方面的重要理论,结果和方法.与经典的组合矩阵等方法不同的是,本文侧重于介绍各种数域上的有限空间理论和方法对于图的组合结构的作用和影响.     

膨胀图在随机算法设计中的应用

介绍了膨胀图的基本理论,组合膨胀与代数膨胀之间的联系,以及膨胀器构造方法等.系统地阐述了膨胀图在随机算法设计中的应用原理和方法.通过对"坏事件"发生的概率上、下界估计,给出了膨胀图在近似算法设计中的应用方法.     

一类交错空间图补空间中的不可压缩、两两不可压缩曲面

利用Menasco W的纽结补空间中不可压缩、两两不可压缩曲面的拓扑图理论,结合三维流形的组合讨论技巧和方法,证明一类交错空间图补空间中具有子午线边界分支的不可压缩、两两不可压缩曲面是穿孔球面.     

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.     

基于断裂点理论和网络加权Voronoi图分析的北京市商业中心辐射域研究

城市断裂点理论作为城市地理学经典理论,与Voronoi图结合将是划分城市商业中心空间势力范围的一种有效工具.尝试对北京市主要商业中心的辐射范围进行了划分,实现了基于道路网络分析的网络Voronoi图和网络加权Voronoi图的构建.对道路系统更新前后构建的网络Voronoi图比较分析,表明构建网络加权Voronoi图是模拟商业中心辐射域的一种有效方法.将断裂点理论与网络加权Voronoi面域图结合,模拟出北京市主城区道路系统更新前后商业中心不同的辐射域空间格局变化,并提取了辐射域覆盖面积、覆盖人口、路网长度、路网密度等信息.实验结果表明:网络加权Voronoi面域图在模拟商业中心辐射域时更加接近地理实际;道路系统更新升级对于商业中心辐射空间格局变化影响明显;商业中心自身规模影响其辐射域的扩张趋势.     

两类合成空间图补空间中的基本曲面

基于合成空间图的定义及基本曲面的性质,利用三维流形组合拓扑的方法,证明了两类合成空间图补空间中具有任意子午线边界分支的基本曲面都是穿孔球面.     

权转移方法在图的染色理论中的应用

图论是数学的重要分支之一,内容丰富,应用广泛,其研究的快速发展直接推动了数学领域的发展.文章在介绍图的染色理论发展的基础上重点论述了权转移方法在染色理论中的应用.     

有机结构理论中的图不变量

本文介绍了有机化学中常用的图不变量,并给出了几个图不变量的矩阵求法及某些公式,是《有机结构理论的图论方法》一文的继续。     

基于有向带环加权多图的线性服务组合

为提升自动服务组合效率,提出在新的服务图结构中实现线性服务组合.该方法使用有向带环加权多图描述服务关系.在深度与广度搜索相结合的组合路径查找过程中,基于语义包容关系将图中节点对之间的多边降级为单边.通过着色和时间戳判断、消除环.给出了具有线性时间复杂度的组合路径查找算法并对其时间复杂度予以理论证明.仿真结果表明:与同类方法相比,该方法能够在线性时间内,在不降低查全率的情况下,发现带环图中的组合路径,并具有查找时间与服务图规模无关的良好可扩展性.     

图的形成原理与图的模式及图的本质

本文沿着图的形成原理这个切入点,运用正确的思维方法和比较证明方法,对四色猜想命题中的图的面与面之间的关系、图的模式、图的本质进行了论证,得出了＂图的形成原理是组合形成整体或整体被分划的过程＂、＂图的面与面之间的关系是组合关系＂、＂图的模式是Cn2组合模式＂、＂图的Cn2组合模式就是图的本质＂的结论。这些结论是本人在研究四色猜想命题方面的重要成果,也是＂张尔光组合说＂的重要组成部分。     

一类3-正则图完美对集的计数

图的完美对集计数理论是图论研究的重要内容之一,此问题的研究具有很强的计算机科学、物理学和化学的应用背景,是一个有生机和活力的研究领域,也是快速发展的组合数学理论中许多重要思想的源泉.构造了一类3-正则新图2-3-nC_6,用嵌套递推的方法,得到了图2-3-nC_6的完美对集数的一个递推关系,再解出这个递推式的通解,从而得到了这个图的完美对集数计算公式.最后又给出这个图完美对集数计算公式的一个组合证明.     

用键合图理论建立浮动自动机系统动力学模型

该文介绍了系统动力学键合图理论的基本思想，并结合火炮自动机的具体特点，以某浮动自动机为实例介绍了用键合图理论把浮动自动机系统表示成统一格式的图形和数学模型的方法和步骤。文中还给出了用所建立的浮动自动机键合图模型编程上机的运算结果，并将计算结果和实测的结果进行了对比。对比表明，计算结果和实测结果基本相符，这说明用键合图理论建立火炮浮动自动机的动力学模型是可行的。键合图理论是系统动力学的新的分支，把它引入火炮自动机的设计中，可以丰富和发展自动机的设计计算理论。     

两类特殊图的1-因子数目

图的1-因子(完美匹配)数目问题是图论理论中的一个重要的问题,一般图的完美匹配计数问题已经被证实为N-P困难问题,因此,只能针对特殊图寻求其完美匹配数目.本文利用线性递推和组合线性递推的方法,给出了两类特殊图的完美匹配数的表达式.为图的完美匹配问题的应用提供了理论支持.     

几类r-冠图的星边染色

图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,得到4类r-冠图的星边色数.     

完全i部图N［(X1,X2,…,Xi),k］计数公式

采用组合卷积公式方法,研究图的S(n)-因子的计数问题.首先获得完全2-部图的恰有k个分支的S(n)-因子的计数公式,并用同样方法获得完全i-部图的恰有k个分支的S(n)-因子的计数公式,从而给出完全i-部图的所有因子数计数公式.进一步研究了完全i-部图的组合恒等式,并通过组合计算技巧,获得了完全i-部图、完全2-部图和完全3-部图的组合恒等武.该研究对图论及组合学具有理论和应用价值.     

基于颜色自相关图的区域定位图像检索

颜色自相关图表示了颜色的空间相关性,在图像检索方法中既有效且计算量小,但是该特征在检索前景较为清晰或背景具有较大面积单色的图像时误检率较高.针对此问题,本文提出了一种基于颜色自相关图的区域定位图像检索算法.该算法使用HSV颜色空间自相关图作为图像的底层特征,通过有效区域定位和二值位图来获得局部特征.最后,综合两种特征进行相似度量.实验结果证明,本文方法具有较高的检索精度,克服了颜色自相关图的片面性,显示了组合特征的有效性.     

用I—X—Y图计算精馏塔的理论塔板数

简述了用 I-X-Y 图计算精馏塔理论塔板数的原理和方法,并通过实例分别用 I-X-Y 图和 Y-X 图对理论塔板数进行了计算比较,结果表明用 I-X-Y 图较用 Y-X 图计算准确.     

图的Normalized Laplacian多项式系数

首先利用图的一级半子图给出了Normalized Laplacian特征多项式系数的一个组合表达式,然后在此表达式的基础上,用组合方法证明了Normalized Laplacian谱和图的结构之间的一系列关系式.     

均匀直线式天线阵方向图分析

分析了常见文献中关于均匀直线式天线阵分析所存在的问题及不足.对均匀直线式天线阵空间方向图进行了详细分析,给出了数学分析计算公式.以实例介绍了如何分析均匀直线式天线阵立体空间方向图.文中的方法及结论也适用于由磁偶极子、短偶极子、半波或全波单元天线组成的均匀直线式天线阵.     

一类带有纽结分支的内在链图

空间图理论是纽结拓扑理论的自然拓广,是当前拓扑学中很活跃的分支。内在链图和内在纽结图是近年来比较新的一个研究领域,也是空间图中的两类重要的图。本文结合内在链图和内在纽结图的性质,构造了一类兼具内在链图与内在纽结图性质的图,带有纽结分支的内在链图,这个图的每个空间嵌入中都包含一个非分离的链,且这个链中至少有一个分支是非平凡的纽结。针对Petersen图P8本文利用两个Petersen图K3.3.1与中间边组成图的方法形成Petersen图中的P8。得到了一类带有纽结分支的内在链图F（104）,并证明了图F（104）是带有纽结分支的内在链图。