关于图测地数的几个问题

本文研究了图的测地数.利用极点必属于测地集的方法,刻画了g(G)=n-1的图G的结构,同时使用图的一些重要参数,获得了图上下测地数的几个新的界.对于有向图D,讨论了g(D)=2的充要条件.     

双圈连通图的L(2,1)-labelling

给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,f(u)-f(v)≥2;当dG(u,v)=2时,f(u)-f(v)≥1.如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)-labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.     

直径为d的超环面网的(d,2n)-控制数

n维超环面网C(dl,d2,…,dn)定义如下顶点集为{(x1,..,xn)|0≤xi<di(1≤i≤n)};每个顶点(xl,…,xn)与(x1±1,x2,…,xn),(xl,x2±1,…,xn),…,(x1,x2,….,xn±1)这2n个顶点相邻.(d,m)-控制数是用来刻画互连网络数据传输某种模式的一个新参数.本文证明了当d=diam(C(d1,d2,…,dn))时,n维超环面网C(d1,d2,…,dn)≠C(3,3,….,3)的(d,2n)控制数为2(n≥3,di≥3,i∈{1,2,…,n}.     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

图和有向图的测地数

图G内的任意两点u和v, u-v测地线是指u和v之间的最短路. I(u,v)表示 位于u-v测地线上所有点的集合, 对于子集SÍV(G), I(S)表示所有I(u,v)的并, 这里u,vÎ S. 图 G的测地数g(G)是使得I(S)=V(G)的点集S的最小基数. 对于有向图D, 类似地可定义g(D). 图G 的测地谱是G的所有定向图的测地数的集合, 记为S(G). G的下测地数g^-(G)=minS(G), 上测地数g⁺(G)=maxS(G). 文中主要研究了连通图G的g(G), g^-(G)和g⁺(G)之间的关系. 同时,还给出g(G)和g(G× K₂）相等的充分必要条件, 从而推广了 Chartrand, Harary 和 Zhang 的相关结论.     

图的L(3,2,1)-标号

无向图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z*的一个映射,满足:对i=1,2,3,只要dG(x,y)=i,则f(x)-f(y)|≥4-i.若一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为k-L(3,2,1)-标号.图G的L(3,2,1)-标号数,记作3λ(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.文中给出了路、圈、树等特殊图的L(3,2,1)-标号数,并给出了一般图的L(3,2,1)-标号数的一个上界.     

关于合理确定集装箱码头装船顺序的算法

如何在给出箱区图和配载图的情况下,根据不同的装船方式,运用计算机程序确定合理的发箱和装箱顺序?本文主要依据实际数据,针对两种在码头实际装船作业中应用性较强的装船方式进行了研究,分别对其做了建立数学矩阵模型,制定合理算法,编写M ATLAB程序等工作,并论证了它们在实际操作中的可行性.本文的研究结果会在集装箱码头的实际装船作业中具有很强的应用性.     

THE BROADCAST FUNCTION VALUE B(23) IS 33 OR 34

1. IntroductionLet G be a connected network of order n. Broadcasting is the process of distributinginformation from an originator to all other nodes of a communication network. The problemaddressed in this paper is under the assumption that only one piece information is to bedistributed, each communication involves exactly two adjacent nodes and takes one unit oftime, and no node is involved into two or more simultaneous communications. Given a nodex as originator, we define the broadcast tim…     

集装箱翻箱问题的模型分析及算法

针对实际生产中集装箱的装船问题,预翻箱是提高装船准确率和装船效率的一个有效方法.本文利用图论知识构建预翻的数学模型,并用加以限制的广度搜索算法计算出翻箱的最少步骤.     

超方体(d,m)的控制数

This paper shows that the (d,m)-dominating number of the m-dimensional hypercube Qm(m≥4)is 2 for any integer d.([m/2] ≤d≤m).