平图的四着色与对偶图的H圈

阐明了平图中的H圈与对偶图顶点四着色的依存关系。提出了平图的顶点四着色和对偶图顶点四着色的具体步骤。介绍了多面体平图的H圈分解与对偶图顶点四着色,以及对偶图的H圈分解与平图的顶点四着色。讨论了平图及对偶图的H圈的个数,森林Fi的个数及顶点四着色方案数。

道路转向延迟的动态对偶图模型

传统的道路转向延迟对偶图表达法缺乏对交通网络时间依赖特性的考虑,不适合动态路径规划问题的求解。本文将时间因素引入到对偶图中,发展了一种动态对偶图模型,将交通路网表达为动态对偶网络,并为之定义了FIFO(先进先出)条件,推导了满足FIFO条件的动态行程计算方法,设计了时间依赖的标号设定最短路径算法。实验结果表明,利用该对偶图模型和动态对偶网络,能有效表达路网转向延迟,在以出行时间为标准的动态路径规划中,基于动态对偶网络的路径规划结果可节省约16%的出行时间。

基于平图的H圈分解的对偶图的四着色

阐明了平图中的H圈与对偶图中的森林Fi及顶点四着色的依存关系,提出了一种基于H圈分解的任意平图的顶点四着色方法。介绍了20面体平图中的90个H圈及对偶图中的90个森林Fi及90种顶点四着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的四着色方案数。

基于属性增强的对偶图实体对齐算法

本文提出结合属性信息的对偶图实体对齐算法针对基于关系感知的双对偶关系图算法中没有考虑到的属性信息进行优化,对属性结构嵌入向量使用图卷积神经网络算法对邻居节点抽取信息,并使用对偶关系图和注意力机制抽取实体对中的关系信息,最后通过结合实体对的关系信息和属性信息的相似度,判断是否为同一实体。针对原算法中识别效率不高的异构知识图谱实体对提升效果明显。在数据集DBP15K的三个跨语言数据集ZH-EN,JA-EN,FR-EN上实验,实验结果验证了对偶注意力以及属性信息对实体对齐方法的有效性。

基于对偶图的道路网络空间邻近关系分析初探

基于对偶图理论提出了一种面向道路网络的空间邻近关系分析方法。1)分析了道路网络空间邻近关系研究存在的问题,引入了道路网络拓扑图及其对偶图描述道路网络的结构和关系;2)引入了邻接矩阵描述对偶图中顶点之间的邻接关系,在邻接矩阵的基础上,定义了道路网络的空间邻近关系;3)提出了一种广度优先搜索算法,计算道路之间的空间邻近关系阶数,并通过实例分析了算法的执行过程;4)开发了一个原型系统,描述了道路网络空间数据组织方式,并通过实例展示了道路间邻近关系的计算结果。实验结果表明:基于对偶图理论的方法能够描述道路网络之间的空间邻接关系;基于提出的广度优先搜索算法能够计算出道路之间的空间邻近阶数。

基于对偶图的对偶树分解的4着色

阐明了对偶图G(p,q,f)4着色的基本思路,提出了n面体的展开图G′(f,s,t)与对偶图G(p,q,f)之间的依存关系,根据这种依存关系,提出了对偶图G(p,q,f)的对偶树及三胞胎树的3种不同的算法,同时提出了这3种算法的适用范围和条件。根据4着色理论,阐明了基于对偶树分解和三胞胎树分解的对偶图G(p,q,f)的4着色方法。文中以20面体为例,介绍了20面体的展开图与对偶图G(p,q,f)之间的对偶关系图和20面体平图的对偶图G(p,q,f)的4着色的全过程,提出了具体的实施步骤,并根据步骤得出相应的结论。

45面体的对偶图2棵树分解四着色法研究

以45面体为例,将p=25,q=69,f=45的对偶图分解为2棵对偶树TA和TB,通过对对偶树TA和TB的顶点2着色,达到对图G(f,q,p)的4着色。讨论了H路径Pi的个数,森林Fi的个数,G(p,q,f)的A区和B区的划分方案数,G(p,q,f)的顶点4着色方案数。

32面体展开图的对偶图G(p,q,f)的4着色

提出了基于对偶图G(p,q,f)的2棵对偶树TA及TB分解的对偶图的顶点4着色方法及对偶树的算法。介绍了32面体展开图的对偶图G(p,q,f)的4着色的全过程。

基于管线对偶图模型的供水管网可靠性分析

为了利用复杂网络理论对供水管网进行结构测度和鲁棒性分析,提出一个新的管网模型——管线对偶图模型.该模型将顺序相连、无大角度转折的同口径同材质管段序列看作统一实体,即管线.将管线抽象为节点,两相交管线对应的节点用边相连,由此形成的无向图即为管线对偶图.使用这一模型对3个城市的供水管网进行结构测度,结果显示,管线对偶图具有明显的无标度特性.利用无标度网络鲁棒性分析方法中的模拟攻击方法,使用3种攻击策略进行实验.结果表明,管网在不同攻击策略下结构变化规律呈现较强的相似性,都会经过初始期、分裂期和崩溃期3个阶段;不同的攻击策略下供水管网进入分裂期和崩溃期的进程差异明显;基于节点度的攻击策略对管网的影响最大,基于节点介数中心性其次,随机攻击对管网的影响最小,高度连接的管线是供水管网中关键和脆弱的部分.对结构测度和模拟攻击的结果进行分析,发现谱隙和进入分裂期的去点率可作为衡量供水管网可靠性的重要指标.针对管线对偶图模型提出的可靠性分析方法可以用于指导供水管网的设计和运维.

对偶图的H圈分解和相应的平图4着色

阐明了平图中的H圈与对偶图中的森林Fi及顶点4着色的依存关系,提出了一种基于H圈分解的任意平图的顶点4着色方法。介绍了20面体平图中的24个H圈及对偶图中的24个森林Fi及24种顶点4着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的4着色方案数。得到任意平图及其对偶图均能分解出H圈和森林Fi,任意平图及其对偶图均为可4着色的。得到了当平图为三角剖分图时,对偶图为多边形组合,H圈个数必大于其对偶图中的H圈的个数。平图为多边形组合时,其对偶图为三角剖分图,H圈的个数必小于对偶图中的H圈的个数。平图中森林Fi的个数或4着色方案数等于对偶图中的H圈的个数;对偶图中的森林Fi′的个数或4着色方案数等于平图中的H圈的个数。

对偶图中的H圈与平图的4着色

阐明了对偶图中的H圈与平图的2棵对偶树的相互依存关系,阐述了平图的4着色与2棵对偶树之间的相互依存关系。平图的顶点4着色以及2棵对偶树的分解决定了对偶图中的H圈,对偶图中的H圈也决定了平图的顶点4着色及2棵对偶树的分解。平图H圈决定了对偶图的2棵对偶树的分解及顶点4着色,对偶图的2棵对偶树的分解及对偶图的顶点4着色决定了平图的H圈的分解。2棵对偶树的2着色等价于平图的顶点4着色,内区与外区的分界线恰好是H圈。提出了多面体平图的H圈的构造步骤和多面体平图的顶点4着色步骤。介绍了12面体平图中30个H圈的构造,对偶图中对偶树的分解、以及对偶树的4着色。解决了任意平图中的H圈的分解方法和计数方法,为解决任意平图中的生成树的构造和计数问题奠定了基础。

平图中的H圈与对偶图的顶点4着色

阐明了平图的4着色及对偶树与对偶图中的H图的依存关系,以及对偶图的4着色及对偶树与平图中的H圈的依存关系。给出了平面H圈和对偶图顶点4着色的基本思路,得到了对偶图与三角剖分图之间的关系,并利用此关系提出了平图及对偶图的H圈及对偶树的分解方法和顶点4着色方法。这两种方法都是通过给出对偶图成平面的面中心的H圈得到对偶树,并对对偶树进行着色而得到的。介绍了46面体平图及对偶图中的H圈及对偶树的各种分解方案和顶点4着色方案。结果表明:任意平图中的H圈必定将对偶图分解为两棵对偶树,且两棵对偶树的2着色等价于对偶图的顶点4着色,从而使kempe四色猜想"证明"中的错误得以纠正。

基于三角剖分对偶图的结构表示模型及其算法

通过提取中轴骨架并对其进行跟踪而获得层次结构图是模式识别中最常用的一种方法。论文提出一种相对骨架的新型结构表示模型“三角剖分对偶图”。利用这种结构表示模型可以从二值图像中直接获得层次结构图,并表达为树的最基本的数据结构。此外,论文还给出了三角剖分对偶图的提取和优化算法,并与骨架表示模型的层次结构图作了比较。

中国建筑师问题与对偶图4着色求解研究

提出了中国建筑师问题,基于森林Fi分解的对偶图的顶点4着色方法提出了森林Fi分解的方法。介绍了p=25,q=69,f=45的对偶图的顶点4着色的全过程,从而给出了求解中国建筑师问题的基本思路。

三正则平面图的对偶图的哈密顿性的注记

本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件

基于对偶图3棵树分解的四着色法

阐明了基于对偶图的3棵树分解的四着色的基本思路。提出了对偶图的四着色方法和被分解的树的算法。介绍了基本信息:22面体的展开图、展开图的对偶图和对偶图平图的对偶图,以及展开图的对偶图的4着色的全过程。

基于有向图与对偶图的概念设计过程模型

针对现有产品概念设计表达及求解很少考虑特性问题,提出了一种基于有向图与对偶图的产品概念设计过程模型。分别对产品功能、抽象特性、结构特征进行描述,通过有向图建立功能与抽象特性的转化关系,将表征特性的有向图转化为对偶图,实现了抽象特性到实体特征的映射。通过边点赋权图对不同子结构评价决策,通过迁移图和布局图得到结构之间的最优布局。最后以一款建筑施工的管桩预应力张拉机概念设计为例,验证了该模型的可行性和适用性。

自对偶图的充要条件

给出自对偶图的充要条件,并利用此充要条件,能构造出所有自对偶图.

两类自对偶图

确定自对偶图的特征结构是尚未解决的图论中的困难问题，本文给出自对偶图的一个必要条件，并利用拟阵理论，构造出两类自对偶图．

大规模网络最大流对偶图算法模型及实现

在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.