关于图的分数k-因子存在性的一些结果

设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。     

可拉伸为任意多边形的自由拉伸算法

针对图像特殊变换问题,即把一个N（N〉3）边形的图像变换为另一个M（M〉N）边形的图像的变形,提出了一种自由拉伸的算法。在该算法的基础上进行适当的变换,不仅能实现基本的几何变换,如缩放、错切、扭曲等,还可以实现N边形的图像变换为半圆或者为N边形（边为曲线）的图像等复杂的图像变换。实验证明该算法取得了很好的效果[1]。     

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设[G]是一个边集为[E]的连通网络。称一个边集合[S?E]是一个限制边割,如果[G-S]是不连通的且每个分支至少有两个顶点。网络[G]的限制边连通度,记为[λ'],定义为[G]的最小限制边割的基数。设[d(v)]表示顶点[v]的度,[ξ=min{d(u)+d(v)-2:uv∈E}]表示[G]的最小边度。称网络[G]是极大限制边连通的,如果[λ'=ξ]。给出了网络是极大限制边连通的一些充分条件。     

给定匹配数的单圈图的最小值

图[G]的广义Randic指标定义为[Rα（G）=uv∈E（G）（dudv）α],其中[α]为任意实数,[du]为顶点[u]的度。顶点数等于边数的简单图称为单圈图。在匹配数等于边数的情况下,通过分类讨论,给出当[-1.39≤a≤-1]时,相应单圈图的广义Randic指标的最小值,并给出相应的结构图。     

N阶整数DCT变换基通用生成算法

为了使DCT变换能够通用,首先通过对DCT变换原理进行研究,发现了变换基系数的取值个数与阶数的关系,并结合余弦函数的性质对其进行了证明;然后以此为基础,提出了一种N(N=2k, k>0,下同）阶整数DCT变换基的通用生成算法（该算法无需对相应的浮点基进行具体分析）;接着通过巧妙排列系数的序号,使得生成的中间多项式具有极强的规律性;最后设计了一个N位M进制数,用来实现N重循环,以穷举所有的可能解,并成功对任意N元多项式组进行了求解。实验结果表明,只要计算机的能力足够强大,应用此算法便可以发现任意N×N整数DCT变换的所有可用基。     

可达性等价于状态方程可满足性的petri网子类

定义了一个petri网子类:PN=(S,T;F,M0),满足条件s∈S→｜·s｜≤1。证明:当目标标识Md>0时,此petri网子类的可达性等价于状态方程Md=M0+ATX的可满足性。同时,当此petri网子类的可达性等价于状态方程可满足性时,可得出如下两点结论:(1)对于满足M0+ATX>0的每个非平凡的非负整数向量X,都■t∈Tx:M0[t>;(2)对于满足M0+ATX>0的每个非平凡的非负整数向量X,X都是PN的一个可执行向量。     

用区域分解法计算最小曲面问题

（?）1.引 言 最小曲面问题即下列变分问题:其中（?）为Rd中有界域,Vg={u∈V:v=g于（?）（?）,V为某个函数空间.此问题及有关问题有重要应用背景,至今仍是一个研究热点,见[1]及其文献.问题（1）的 Euler方程为下述非一致非线性椭圆方程边值问题问:[3]中证明了当 时,（1）有解u∈Bv（（?））,其中BV（（??））为（?）上的有界变差函数类,其定义见下节.     

瑞萨科技发布8至32位CISC微控制器开发工具E100 Emulator

瑞萨科技公司（Renesas Technology Corp．）宣布，推出“E100 Emulator”全规格仿真器，以支持新的M16C系列、H8S系列和其他8至32位CISC（复杂指令集计算机）微控制器系列，从而增加了该公司的微控制器开发工具阵容。[第一段]     

一个新的证明网定义及合理性

本文给出一个新的线性逻辑的证明网的定义并证明了所定义的证明网是线性逻辑的自然推理．和Ｇｉｒａｒｄ的原定义相比,使用本文给出的定义来判定一个证明结构是否为证明网的时间复杂度为Ｏ（ｎ＊ｎ）,并且在证明所定义的证明网是可矢列化时更加自然和简单．     

基于Petri网的顺序资源分配系统活性的一个性质

具有多资源需求和柔性加工路径的顺序资源分配系统(Sequential Resource Allocation Systems with Multiple Resource Acquisitions and Flexible Routings,C/D-RAS)是一类较复杂的、更为一般的资源分配系统。考察了两个与 C/D-RAS密切相关的活性问题。借助这两个C/D-RAS的Petri网模型来定义标识S3 PGR2网对((N1,Mm),(N2,M02),由标识S3 PGR2网中资源种类、数量的守恒性和变迁使能的一个充分必要条件,证明(N1 ,M01)和(N2,M02)的合法变迁发生序列是一致的,据此得出的最终结论是(N1,M01,)和(N2,M02)具有相同的活性。最后,简要提及本结论的应用。     

Managing e-transformation in the public sector: an e-government study of the Inland Revenue Authority of Singapore (IRAS)

Continuous organizational transformation is becoming a common phenomenon as public agencies rapidly embrace new information technologies (IT) to streamline and re-invent their obsolete operations. However, due to the overwhelming extent of the necessary changes as well as the sheer diversity of stakeholders involved in transforming corporate functions, practitioners are finding it difficult to manage the level of dynamism required in the effort. In an attempt to shed some light on the phenomenon of managing e-transformation, this paper examines in-depth an e-government initiative. Through the study of how one organization in the public sector adapts to the dynamic customer relations brought about by e-transformation, the case serves to identify the governing factors for successful organization–stakeholder relations, and how these may have a bearing on the development of effective e-transformation strategies. An important contribution of this study is the proposal of a development model of relationships in organizations for an understanding into how organization–stakeholder relationships can be efficiently managed to bring about an effective overhaul of business processes.     

On the inverse Hough transform

In this paper, an inverse Hough transform algorithm is proposed. This algorithm reconstructs correctly the original image, using only the data of the Hough transform space and it is applicable to any binary image. As a first application, the inverse Hough transform algorithm is used for straight-line detection and filtering. The lines are detected not just as continuous straight lines, which is the case of the standard Hough transform, but as they really appear in the original image, i.e., pixel by pixel. To avoid the quantization effects in the Hough transform space, inversion conditions are defined, which are associated only with the dimensions of the images. Experimental results indicate that the inverse Hough transform algorithm is robust and accurate     

拟人机器人TH-1手臂运动学

拟人机器人手臂的主要特点是它的运动功能，能够实现握手、行走时掌握平衡等动作．本文 主要针对自行设计的具有转摆结构的拟人机器人TH-1手臂机构进行了运动学分析，为其控 制提供数学基础．提出了坐标变换、三角变换等方法，巧妙求解出拟人机器人TH-1手臂逆 向运动学的解析表达式．建立了仿真软件平台，验证了运动学正逆向方程的有效性．     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

Index transforms of a symmetrical matrix: Application to the geosciences

Compressing symmetrical or quasi-symmetrical information can decrease data redundancy, save storage and network resources, and speed up the real-time transmission of symmetrical data over a network. During the past few decades, the compression and decompression of a symmetrical matrix, the index transform formulae have been used to calculate the post-compression indices from the original indices. However, the index inverse transform formulae that are used to calculate the original indices from the post-compression indices have yet to be derived. The algorithms used to decompress these matrices have never been very efficient, such as the bi-layer loops algorithm, which is proportional to the time complexity factor O(n²). Using the index inverse transform formulae deduced in this paper, the corresponding time complexity factor can be reduced to O(1), which is a significant improvement. This paper analyses the difficulty in deriving an index inverse transform formula. The formulae for the index transform and its inverse transform of the column-compression of the symmetrical matrix are proposed and can be stated as five theorems. Based on those formulae, the relative running efficiency of two decompressions on the covariance matrix of the positions and velocities of ITRF2000—ALASKA Stations is analyzed. It is concluded that two redundant fields in the International Terrestrial Reference Frame (ITRF) covariance matrix file can be removed. Other related issues for further study in the geosciences are also raised.     

Optimal Embeddings of Paths with Various Lengths in Twisted Cubes

Twisted cubes are variants of hypercubes. In this paper, we study the optimal embeddings of paths of all possible lengths between two arbitrary distinct nodes in twisted cubes. We use TQ_n to denote the n-dimensional twisted cube and use dist(TQ_n, u, v) to denote the distance between two nodes u and v in TQ_n, where n ges l is an odd integer. The original contributions of this paper are as follows: 1) We prove that a path of length l can be embedded between u and v with dilation 1 for any two distinct nodes u and v and any integer l with dist(TQ_n, u, v) + 2 les l les 2ⁿ - 1 (n ges 3) and 2) we find that there exist two nodes u and v such that no path of length dist(TQ_n, u, v) + l can be embedded between u and v with dilation 1 (n ges 3). The special cases for the nonexistence and existence of embeddings of paths between nodes u and v and with length dist(TQ_n, u, v) + 1 are also discussed. The embeddings discussed in this paper are optimal in the sense that they have dilation 1     

Channel assignment with separation for interference avoidance in wireless networks

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1相似文献   

AVS-M中基于准零块检测的快速率失真算法

一个4×4块在变换、量化后各元素的绝对值和若不大于1,称该块为“近似零块”或“准零块”,AVS-M编码时就认为该4×4块的残差全为零,对该块的变换、量化、反量化、反变换运算都是没有必要的,在实际的低码率应用中,一般有70%-90%的4×4块变换、量化后为准零块。提出一种准零块的检测方法,只额外增加对非准零块各元素平方和(SSD)的计算,减少了率失真中的70%-90%变换、量化、反量化、反变换运算,编码性能基本不变。