共查询到20条相似文献,搜索用时 31 毫秒
1.
用标号法实现单源最短路径问题的迪杰斯特(dijkstra)算法 总被引:2,自引:0,他引:2
最短路径问题(最低费用问题)广泛应用于计算机图论,数据结构,数据通信等领域。本文主要通过对迪杰斯特(djkstra)算法的分析和改进实现来应用贪心算法解决实际问题。 相似文献
2.
马旭东 《新疆师范大学学报(自然科学版)》1990,(2)
时至今日,寻找一个图是否有优美标号和序贯标号的充要条件的问题仍是开的。 实际中,寻找一个稍大一点的图的优美标号和序贯标号是一件困难的事。本文对这两件工作给出了一种统一的算法,使得我们利用电子计算机可解决:一、验证一个图是否有优美标号和序贯标号。二、若有,则给出所有的优美标号和序贯标号。 本文用BASIC语言给出了本算法的一个程序。 相似文献
3.
图的圈带宽和问题即为求图G的一个在圈上的标号,并且使得边的总长尽可能地小,用BSc(G)表示.给出了BSc(G)的一个上界并讨论了BSc(G e)与BSc(G)的关系,其中eE(G). 相似文献
4.
5.
6.
7.
通过构造方法,给出了平面网格图的并图P(n1,n2,…,nm)的奇优美标号和奇强协调标号以及其k-优美标号和k-强协调标号.从而证明这类图是奇优美图和奇强协调图. 相似文献
8.
9.
主要研究了树的优美标号,奇优美标号,(k,d)-优美标号,边魔幻全标号,反魔幻全标号,和谐标号及幸福标号之间的关系. 相似文献
10.
研究含边不交回路网络的中心选址问题,给出了一个求其最小直径支撑树的破圈算法,由此得到求其中心的O(mn)阶算法,这里m是网络中含回路的个数。 相似文献
11.
杨爱民 《山西大学学报(自然科学版)》1996,19(1):22-26
如所知,确定一般图的侧廓,已经被证明是一个NP-完备问题,对于(m,n)-构形,本文确定了其侧廓并给出了相应的最优称号。 相似文献
12.
关于毛毛虫的优美问题有不同的解决方法,其中毛毛虫优美标号的逐步构造方法简便易行,然而,在文献中由于其证明有些漏洞而往往引起读者对这种方法的可靠性的怀疑,本文将补充这个漏洞. 相似文献
13.
针对网络图标号问题,在无向图边-友好标号的基础上,提出了有向图出边-友好标号的概念.利用标号矩阵来研究网络图标号问题,并通过引入子矩阵设计、矩阵变换等方法技巧,确定了完全网络图的出边-平衡指数集.同时利用标号矩阵可以得到相应的标号网络图. 相似文献
14.
一类单圈图的优美性和平衡性 总被引:1,自引:0,他引:1
设L为简单无向图G的一个顶点标号,L称为图G的优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,2,…,|EI|}的一个单射;(2)由L’(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L’是G的边集E到{1,2,…,|EI|}的一个双射.进一步,若存在正整数c,使得对每一个uv ∈ E(G)满足L(u)≤c〈L(v)或L(w)≤c〈L(u),则称L为图G的平衡标号,其中c为平衡特征.主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征. 相似文献
15.
高振滨 《哈尔滨商业大学学报(自然科学版)》2005,21(6):781-783
在图论的研究中,图的标号问题是在二十世纪六十年代提出的 ,人们根据应用的需要提出了许多关于简单图的标号猜想.在猜想和实际应用中,涉及到最多的是树.Chen et al定义了香蕉树,在此讨论了该树的奇优美标号以及在一些情况下的伪优美标号. 相似文献
16.
17.
18.
19.
左光纪 《青海师范大学学报(自然科学版)》2005,(4):1-4
一个(p,q)-图G称为是(k,d)-算术的,若它的顶点可标以不同非负整数,使得它的边的赋值(由它的端点标号之和得到)能排成算术级数k,k+d,k+2d,…,k+(q-1)d.本文综述了算术图的有关结果. 相似文献
20.
容青 《广西师范学院学报(自然科学版)》2009,26(2):37-40
设u、v是两个固定顶点,用b条内部互不相交且长度皆为a的道路连接u、v所得的图用Pa,b表示.K. M. Kathiresan证实P2r,2m-1(r,m皆为任意正整数)是优美的,且猜想:除了(a,b)=(2r-1,4m-2)外,所有的Pa,b都是优美的.杨元生教授已证实P2r-1,2m-1是优美的,并且证实了当r=1,2,3,4,5,6,7,9时P2r,2m也是优美的.该文证实当r=8,10时P2r,4m+2也是优美的. 相似文献