有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。

从有向图的通路矩阵生成有向图的全部有向回路的一个算法

本文在定义了点边矩阵的基础上,形成了通路矩阵,证明了通路矩阵生成有向回路的条件。由此提出一个生成有向图的全部有向回路的算法。该算法能系统地,无重复地生成有向图的全部有向回路。

从有向图的关联矩阵寻找其全部有向回路的机辅算法

本文研究了有向图的有向回路、单连支有向回路、多连支有向回路等与其关联矩阵的关系,所有单连支有向回路通过“并”运算不能生成任何一个有向回路的性质,以及单向割集不构成任阿有向回路的性质等。在这些理论研究的基础上,本文提出了通过有向图的关联矩阵寻找图的全部有向回路的机辅算法。

生成有向图的有向通路和有向回路的一个新算法

本文首先定义了顶点的边、度关系矩阵，由此形成通路矩阵。证明了通路矩阵生成有向通路和有向回路的条件，提出了一个系统地。

关于生成有向图的全部有向回路的回路向量空间法

本文提出一个由有向图的(1)有向回路基集或(2)定向回路基集,通过线性组合,生成全部有向回路的算法。文中证明了一条“点数边数相等”原则。根据此原则,得到一个识别有向回路的简单方法,从而使算法的计算时间与对应的无向图算法基本相同。

生成有向图中全部简单回路的一种有效算法

在研究有向图中全部简单回路现有算法的基础上,综合各算法的优点提出一种新的算法。算法的主要思想是对图中顶点进行深度优先搜索,在搜索过程中采取措施避免同一回路的重复出现,同时记录有用信息避免对顶点的重复访问,从而提高算法的效率,还给出了算法的证明和实例应用。算法结构清晰简单,方便转化为计算机程序。

生成有向图中全部简单回路的一种新算法

提出了生成有向图中全部简单回路的一种新算法.算法的主要思想是对图中顶点进行缩减,在缩减过程中巧妙地利用字符串标记保存图中原有信息,不断减少图中顶点的数量,最终将图缩为一点,逐步得到全部简单回路.这种缩减过程隐藏在矩阵运算中,在运算中不断简化矩阵,从而降低了运算复杂度,提高运算效率.此算法生成的回路中不包含重复的回路,算法结构清晰,易转化为计算机程序.文中给出了算法的详细证明和实例应用.

一种求网络所有回路的矩阵方法

本文利用网络矩阵间的两种特殊运算,得到了一种求网络所有有向回路和所有无向回路的矩阵方法。由本方法所形成的计算机算法属多项式型算法,具有有效性,且对边数多、回路数多而节点相对少的网络更为适用。本文举例对方法进行了说明,并表明算法是收敛的。

求解大规模稀疏有向图回路的多线程并行算法

传统的基于深度优先遍历的回路求解算法限于计算机内存无法对大规模图进行求解,而已有的分布式图计算系统需要借助计算机集群,成本较高。针对此问题,给出一种可在普通计算机上求解大规模有向图所有回路的多线程并行算法。该算法根据顶点的出度,首先删除出度为0的顶点,然后采用多线程并行求解包含出度较大的顶点的回路,最后使用串行算法求出图剩余部分的回路。实验表明,此算法能够在普通计算机上求得大规模有向稀疏图的所有回路。

有向图的所有回路的求法

现在有一些文献对有向图的回路做了一些讨论,一般采用了递归的方法.本文利用邻接矩阵存放有向图,用非递归的方法求有向图的所有回路.

基于图论的路网交通检测器之布点

为获取各路段的交通流量,将路网检测器布点问题转变成寻求有向图的流控制子图的问题.首先将任意路网抽象为有向图,定义弧的度表征路段的重要性,证明完全有向回路图(CCG)的若干结论后给出CCG最小流控制子图的获取算法,同时给出有向图非回路部分的流控制子图获取方法,进而提出能在任意路网上进行检测器优化布点的完整算法.算例选取广州火车东站附近的路网,结果验证了所提出的方法的有效性.

n·C_(2P)的优美性

是一个有向ｍ回路，ｎ个恰有一个公共点组成的图，记作ｎ·证明了ｎ·是优美图，给出了ｎ· 是优美图的必要条件，并猜想：当ｎ≡０（ｍｏｄ２）时，ｎ·是优美图。

有向图2k·_5及2k·_7的优美性

杜之亭（１９９４）中提出的猜想：在ｎＣ２ｐ＋１（ｐ∈Ｎ），在ｎ≡０（ｍｏｄ２）时是优美图。证明了，当ｐ＝２。

再论图n·_3的优美性

进一步证实了 ,两个无交有向图n·C 3 和n·C ′3 之并的优美性及n·C 3 的公共点和n·C ′3 的公共点用两个方向相反的弧连接而得到的图的优美性 。

关于两两无交有向图n·_3之并的优美性

文章中证实了四个两两无交有向图n.3之并的优美性和六个两两无交有向图n.3之并的优美性,并且我们猜想:偶数个两两无交有向图n.3之并为优美图.

求网的S-不变量的一种图算法

本文提出了一种新的求解网的S-不变量的方法。这种方法的基本思路是把一个网看作一个有向图,通过寻找网N的S-封闭基本有向贯通路簇或S-封闭基本有向回路簇,可以得到封闭重数方程组,求此封闭重数方程组的解就得到此网N的所有极小S-不变量。

关于四个两两无交有向图n·_3之并的优美性

文章中证实了四个两两无交有向图n·C 3之并的优美性及两两无交有向图n·C 3,n·C 3,2n·C 3之并的优美性,标号设计采用了对顶头数n分段设计方法.

一类特殊逆M-矩阵判定

讨论了具有一有向回路的非负矩阵的性质,给出了与其逆有相同零位模式的条件,研究了该矩阵为逆M-矩阵的条件,间接地给出了非负三对角矩阵为逆M-矩阵的充分必要条件。

虚拟漫游环境中基于矢量的快速碰撞检测算法

从虚拟漫游角度出发,将场景中的碰撞检测转化为视点与三角形的碰撞问题,提出一种基于矢量判别的快速碰撞检测算法。该算法通过位向因子和有向回路的方向来判断视点是否与三角形碰撞,从而避免复杂的余弦函数、移动距离等计算,加快检测速度。实验结果表明,对于大型复杂场景,该算法的检测效率优于其他基于余弦函数的视点与三角形碰撞检测算法。

基于有向通路的潮流跟踪新算法

在可以处理并行边的有向通路生成算法基础上,提出了一种功率分摊原则。应用该分摊原则,可以计算出输电线路的功率组成和发电机与负荷之间的实际功率输送关系,从而为输电服务收费提供合理的依据。运用IEEE14节点系统证实了该算法的实用性和有效性。