求受顶点数限制的最短路径问题的一个算法

提出了求受顶点数限制的最短路径问题的一个算法,与现有的算法相比,该算法效率较高,时间复杂度为(O(k-2)n2)(k是受限制的顶点数,n是图中顶点总数);而且该算法比较简单,易于描述、实现和理解。

顶点数不超过7的图按参数A(H)的完全分类

本文根据图的直径 ,通过对图H联系数集的分析 ,给出了顶点数不超过 7的所有 1 2 5 6个图按A(H) =0 ,1 ,2 ,3,4的完全分类 .

顶点数不超过7的A(H)=3图

根据图的直径大小,通过对图H联系数集的分析,证明了顶点数ν≤7的A(H)=3图是惟一的,即肯定了满足A(H)=3最小图的惟一性.

关于图的连通度、宽直径、顶点数函数的讨论

FrankHsuD博士 (1994年 )中提出了w_距离 (w_distance)和w_直径 (w_diameter)的概念 ,介绍了“函数h(k ,d ,n)” ,其中的参变数包含连通度k ,最大直径d和顶点个数n .该文对这个函数进行了讨论 ,给出了部分结果 .

平面体截交线边数和顶点数的计算模型研究

分析单个截平面截切平面体时产生的截交线边数和顶点数,总结其计算规律。在此基础上,分析多截面平面体截交线的边数和顶点数,设置截平面之间的交线数量参数,建立计算模型。通过验证计算模型的有效性,确定计算模型的适用性,以期辅助解决工程中截切体投影视图的难题。

r-正则图的顶点数、边连通度和k-对等图

证明了如下结论:设n为偶数,r和k为奇数,n＞r＞k＞0,λ≥2为整数,λ*=2[(λ)/(2)]+1,r-λ*k＞0,G是有n个点、边连通度为λ的r-正则图,若n＜(r+2)(k+1),则G是k-对等图.

一种求受顶点数限制的最短路径的新算法

提出了一种基于逆邻接表求受顶点数限制的最短路径的新算法,其时间复杂度为O((m-2)*w)(m是受限制的顶点数,w是有向图中弧的条数),优于同类算法。采用逆邻接表作为图的存储结构,该算法很容易实现。

r-正则图的顶点数、边连通度和k-覆盖图

设 n为偶数 ,r和 k奇数 ,n>r>k>0 ,λ≥ 2为整数 ,λ* =2 [λ/2 ] +1 ,r-λ*k>0 .G是有 n个点、边连通度为 λ的 r-正则图 .若 n<( r+2 ) ( k+1 ) ,则 G是 k-覆盖的 .

关于四维正方体的顶点数、棱数、面数、三维正方体数

我们知道,一个三维正方体有顶点数、棱数、面数.如果设想存在一个四维正方体,它的顶点数、棱数、面数、三维正方体数为多少呢?这是我们在测试中学生数学创造能力时使用的问题.现将我们以及学生对该题的解法整理出来,供大家参考. 解法一(对应法)因为二维正方形有2~2个顶点,当向上增加一个方向时。

树图中进攻性联盟的顶点数上界

给出简单连通树图中进攻性联盟的顶点数α0(T(G))的上界(2τ(G))/3,强进攻性联盟的顶点数α0(T(G))的上界(5τ(G))/6,全面进攻性联盟的顶点数γ0(T(G))的上界└(2τ(G))/3┘及全面强进攻性联盟的顶点数γ0(T(G))的上界└(5τ(G))/6┘.

调和平衡图直径与顶点数的关系

如果非平凡连通图G中任意的顶点v都对应G中唯一的顶点,使d(v,)=diam(G),则称G为平衡图.若平衡图G中由边uv∈B(G)可推出∈B(G),则称G为调和平衡图.本文证明了顶点数为n直径为d(d≥5)的调和平衡图G当G≌C_n时有关系式n≥3d.

奇数度正则图的顶点数、边连通度和k-消去图

设 n为偶数 ,r和 k为奇数 ,n>r>k>0 ,λ≥ 2为整数 ,λ*=2 [λ/ 2 ] +1 ,r-λ*k>0 .G是有 n个顶点、边连通度为λ的 r-正则图 .若 n<( r+2 ) ( k+1 ) ,则 G是

圈与路的_r-冠图的顶点_(PI)指数

设图G=（V,E）为简单连通图,称PIv（G）=∑e=uveE（nu（e｜G）＋nv（e｜G））为图G的顶点PI指数,其中nu（e｜G）表示图G中到边e=uv的端点u的距离小于到端点v的距离的顶点数。根据圈与路的r一冠图Ir（Cn）与Ir（Pn）的对称性结构特征,研究了此两类图的PI指数的计算公式。

关于顶点Folkman数的新不等式(英文)

对于无向简单图G及正整数a1,…,ak,记G→(a1,…,ak)v当且仅当对于图G的任意一种顶点k染色,一定对某个i∈{1,…,k}存在顶点全染着颜色i的完全子图Kai.对于p>m ax{a1,…,ak},定义Fv(a1,…,ak;p)=m in{V(G):G→(a1,…,ak)v,Kp G}为顶点Folkm an数.证明关于顶点Folkm an数Fv(k,k;k+1)的新的迭代不等式,并推广K olev和N enov的一个关于多色顶点Folkm an数的不等式.

两个多色顶点Folkman数的界

对于正整数a1,a2,…,ar以及无向简单图G,当且仅当对G的任意一种顶点r着色,都对某个i∈{1,2,…,r}存在顶点都着有颜色i的ai阶的完全子图,则记G→(a1,a2,…,ar)v。对于k>max{a1,a2,…,ar},顶点Folkman数定义为Fv(a1,a2,…,ar;k)=min{|V(G)|:G→(a1,a2,…,ar)v,Kk G}。借助于计算机得到了18≤Fv(2,2,2,3;4)≤Fv(2,3,3;4)≤30。

顶点Folkman数的上界(英文)

证明关于顶点Folkman数上界的新不等式.特别地,用构造性方法证明:对于任意满足0<r<1/2log23-3/4的实数r,存在N(r)>0和c(r)>0使得Fv(k,k;k+1)≤c(r)(k-1)1/4log2(k-1)-r对任意的k≥N(r)成立,其中N(r)和c(r)都是只依赖于r的常数.

关于图的顶点划分数

该文讨论了无爪图的顶点划分数,给出了完全n部图的顶点划分数的计算公式,最后证明了任意图的点线荫度不大于它的边线荫度且不等式是精确的.

凸多面体中顶点数、棱数、面数之间的关系

你认识大数学家欧拉吗?凸多面体中顶点数、棱数、面数之间的关系是欧拉研究过的问题.让我们也来试着研究一番吧! 一、试一试,你一定行! 请同学们按照下表进行自主探究.