扩展双星树的 Wiener-E 指标和 Wiener-O 指标

扩展双星树（T（n）n1,n2）是 n－1长路径的两端点分别联结 n1条悬挂边和 n2条悬挂边所得到的图。论文根据扩展双星树的结构特征,研究了扩展双星树的类Wiener指数,给出了一般计算公式。     

光圈

光圈是镜头内由若干金属薄片构成的一个可调节大小的圆孔,就像可变化的一扇窗户．用来控制通过镜头时光线数量（面积）的大小。光圈的大小用光圈系数F表示．F值数字越小．表示光孔越大．通过镜头的光线就越多;F值数字越大,表示光孔越小,通过镜头的光线就越少（图例1）。     

有限域上定长序列的最短线性递归长度分布

研究有限域F（q）上任意给定长度的序列的最短线性递归长度的分布.对任意正整数n和0≤l≤n,计算出了长度为n、最短线性递归长度为l的序列个数,指出了对于固定长度为n的任意序列,其最短线性递归长度大部分情况下等于n/2或n/2＋1,即其最短线性递归长度的分布一般都集中在长度的一半位置.     

泡形互连网络的条件连通性度量

n维泡形网络是设计大规模多处理机系统时最常用的互连网络拓扑结构之一,它以n维泡形图Bn为数学模型。F是连通图G的顶点子集,使得G-F不再连通且G-F的每个连通分支都有至少有n个顶点的F的势叫做G的Rk连通度。Rk连通度是衡量网络可靠性的一个重要参数。一般来说,网络的Rk连通度越大,其可靠性越高。研究了n维泡形网络的 k连通性;证明了在n维泡形网络中,当n≥3时,其R1连通度为2n-4;当n≥4 时,其R2连通度为4n-12。     

闪光灯 相机的第二双眼

闪光灯必备常识 1．闪光灯指数 闪光灯指数（GN）是衡量闪光灯功率的标准之一。GN值越大,表示闪光灯的功率越大。同时,GN值还能帮助我们计算使用闪光灯时的光圈大小。公式是：GN值=光圈×距离（以ISO100为基准）。例如闪光灯GN值为20,当与被摄物体距离五米时,光圈设定为F4就能获得正常的曝光。如果拍摄距离增加到10米,那么光圈就需要增加到F2——我们都知道,光圈数字越小,光圈越大。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

前置放大器的NF图及其应用

<正> 众所周知,衡量一个前置放大器噪声大小最常用的指标是噪声系数F,定义为F=放大器的总输出噪声功率/源电阻R_s产生的输出噪声功率用对数表示称为噪声因数,即NF=1O1ogF.噪声系数也可以用放大器输入端的噪声功率表示(见图1),即:? (1)式中;4KTR_sΔf为源电阻R_s     

基于B_树的证书吊销实用系统

针对公钥基础设施PKI中证书吊销问题,提出一种B_树解决方案,将查询与更新时的最大时间复杂度始终保持在O（logd（（n＋1）/2）＋1）量级,与其他方案相比,当数据量特别大时,更能显示其优越性,同时介绍基于B_树的证书管理方案。实验结果表明,该方案对工程实现具有一定指导意义。     

TD-H2H:时序图上的最短路径查询

道路网络上的最短路径查询是一个已经被广泛研究的基本问题。现有的研究通常将道路网络建模为静态图,查询给定节点间距离最短的路径。然而,道路网络具有时序性,将道路网络建模为时序图更符合实际情况。与静态图相比,时序图的规模更大,结构也更为复杂,增加了时序最短路径的查询难度。时序最短路径是指在给定出发时间下,时序图上源节点和目的节点之间旅行时间最短的路径。因此,时序最短路径的结果受给定出发时间影响,为时序最短路径的查询带来了新的挑战,传统的最短路径算法不适用于时序最短路径的查询。将道路网络建模为时序图,并基于树分解提出了TD-H2H索引,利用该索引可以快速准确地实现时序最短路经查询。首先,研究了时序图上的树分解问题,提出时序树分解算法,将图结构转变为树结构。然后,通过树分解快速确定索引结构,提出了高效的索引构建算法,用以构建TD-H2H索引。最后,基于TD-H2H设计了高效的最短路径查询算法TD-OAI。在4个真实公开的数据集上与现有算法进行了实验,结果表明提出算法的查询效率优于现有算法1～2个数量级,证明了提出算法的有效性和效率。     

联图W_4+C_n的交叉数

联图G+H表示将G中每个点与H中的每个点连边得到的图。在Klesc M.给出联图W3+Cn的交叉数的基础上,应用反证法和排除法得到了联图W4+Cn的交叉数为Z(5,n) + n +|n/2|+ 4(n≥3)),并在Zarankiewicz猜想成立的前提下,根据证明,提出对Wm+Cn的交叉数的一个猜想:cr(Wm+Cn)=Z(m+1,n)+|m/2||m-1/2||n/2|+|m/2|+|n/2|+2,n≥3。其中Z(m,n)=|m/2||m-1/2||n/2||n-1/2|,m,n为非负整数。     

单圈图毁度的一个算法

图G的毁度定义为r(G)=max{ω(G-X)-|X|-m(G-X):X?V(G),ω(G-X)>1},其中ω(G-X)表示G-X的连通分支数,m(G-X)表示G-X的最大连通分支的阶。对于一般图G,其毁度的计算为NPC问题。将单圈图的毁度计算问题转化为树或圈的计算问题,从而提供了一个单圈图毁度的计算方法。     

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

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

A Conjecture on Wiener Indices in Combinatorial Chemistry

Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents an atom of the molecule, and covalent bonds between atoms are represented by edges between the corresponding vertices. This polygonal shape derived from a chemical compound is often called its molecular graph, and can be a path, a tree, or in general a graph. An indicator defined over this molecular graph, the Wiener index, has been shown to be strongly correlated to various chemical properties of the compound. The Wiener index conjecture for trees states that for any integer n (except for a finite set), one can find a tree with Wiener index n. This conjecture has been open for quite some time, and many authors have presented incremental progress on this problem. In this paper we present further progress towards proving this conjecture—through the design of efficient algorithms, we show that enumerating all possible trees to verify this conjecture (as done by all the previous approaches) is not necessary, but instead searching in a small special family of trees suffices, thus achieving the first polynomial (in n) time algorithm to verify the conjecture up to integer n. More precisely, we (i) present an infinite family of trees and prove various properties of these trees, (ii) show that a large number of integers, up to at least 10⁸ (compared with the previous best 10⁴) are representable as Wiener indices of trees in this succinct family, (iii) provide several efficient algorithms for computing trees with given Wiener indices, and (iv) implement our algorithms and experimentally show that their performance is asymptotically much better than their theoretical worst-case upper bound.     

Total coloring of planar graphs with maximum degree 7

In the paper, it is proved that a planar graph of maximum degree Δ?7 is (Δ+1)-totally-colorable if no 3-cycle has a common vertex with a 4-cycle or no 3-cycle is adjacent to a cycle of length less than 6.     

级连层次图的网络最大流算法研究

给出一种通过构造网络级连层次图的方法,来间接求出最大网络流的算法。对于给定的有n个顶点,e条边的网络N=G,s,t,C,该算法可在On2时间内快速求出流经网络N的最大网络流及达最大流时的网络流。     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

Variable neighborhood search for extremal graphs: IV: Chemical trees with extremal connectivity index

By means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization, we established the structure of the chemical trees possessing extremal (maximal and minimal) values for the Randić connectivity index (χ). These findings were eventually corroborated by rigorous mathematical proofs. As could have been anticipated, the n-vertex tree with maximum χ is the path. The n-vertex chemical tree with minimum χ-value is not unique. The structures of such chemical trees (which should be considered as the graph representations of the most branched alkanes) are fully characterized.     

基于关系模型的子图同构检测算法设计与实现

在图分解索引(GDI)算法的基础上,利用关系模型存储图的分解信息,采用B*树对子图结点度进行索引,由此提出一种新的子图同构检测算法——关系图分解索引(RGDI)。实验结果证明,与GDI相比,RGDI可节省更多存储空间,得到的候选集更准确,且子图同构检测效率更高。     

Sea Ice Classification of Polarimetric SAR Imagery based on Decision Tree Algorithm of Attributes’ Subtraction

Polarimetric SAR image usually has multiple polarization attributes,and the imaging brightness of different sea ice types in different polarization modes is obviously different.A decision tree (SDDT) analysis method on attributes’ subtractions suited for sea ice classification of polarimetric SAR imagery is proposed in this paper.The subtractions between any two attributes based on a given n attributes are calculated.Then their classification ability and optimal divided threshold are calculated.The most effective attribute is discovered and used to construct classification tree.According to this strategy,it equal to find the optimal subtraction attributefrom n+C ² n features for classification,which include original n attributes and C²n subtraction attributes.In addition,we use GainRatio to compare the classification ability between different attributes firstly.When there are several attributes with a same GainRatio,we consider the width of the split point (ΔWidth) and the total width of the attribute (TotalWidth) and define a classification ability index ClassifyAbility=GainRatio* ΔWidth/TotalWidth.By calculating and comparing ClassifyAbility index,an optimal attribute with the largest attribute classification abilitycan be selected.Experiments show that the accuracy of SDDT algorithmhas ten percent higher than that of C4.5 algorithm using a same training samples.     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.