图的生成树分解

一个图Ｇ称为是ｍ－ＳＴ可分解的,如果Ｇ能分解为ｍ个边不交生成树的并,本文研究了一个图是ｍ－ＳＴ可分解的若干性质,并证明了两类平面图是２－ＳＴ可分解的。     

广义轮图的色多项式唯一性

本文证明了:当k≥0,n≥4为偶数时,广义轮图θ_n,k色多项式唯一。同时,也用较简单的方法证明了:对于一个图G,其色多项式为P_λ(G)=λ…(λ-q+1)·(λ-q)^n-q当且仅当G为n阶q-树。     

几种复合图生成树个数的一般求法

若一个图能够由某一个或某几个运算作用于不相交的图上而得到，则称该图为复合图．记ｔ（Ｇ）为图Ｇ的生成树个数，Ｈ（Ｇ）为图Ｇ的Ｋｉｒｃｈｈｏｆｆ矩阵，用“ｏ”表示图的某种运算，如“＋”，“×”，“合成”等，本文研究了Ｈ（ＧｏＧ′）与Ｈ（Ｇ），Ｈ（Ｇ′）的特征值关系，给出了ｔ（ＧｏＧ′）的一般性公式，提供了几种复合图生成树个数的一般性公式，提供了几种复合图生成树个数的一般求法，大大推广了［２，３］的结果，同时简化了许多图类生成树个数表达式的求法．     

扩展de Bruijn图的生成树和广播

扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为[log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.     

基于电网络技巧计数一类平面自相似图的生成树数目

Sierpiński多面体是Sierpiński三角形的三维近似,Sierpiński金字塔自相似图是Sierpiński四面体的1-骨架。本文受Sierpiński金字塔图的构造启发,研究一类构造上极为相似的平面自相似图。基于图的自相似性特点和电网络理论技巧,得到这类自相似图的生成树的计数公式及生成树增长的熵值。     

K1,r—free图的次限制树多项式算法

设Ｇ＝（Ｖ，Ｅ）为一连通图，ｄ〉０整数。Ｇ中存在生成对Ｔ，使得Δ（Ｔ）小于ｄ吗．这一问题已被证明是ＮＰ－完全的，故不太可能有多项式解法。本文证明了当Ｇ是Ｋ１，ｒ－ｆｒｅｅ时，则有Ｏ（ｎ＾２）的算法求出Ｇ生成树Ｔ，使Δ（Ｔ）≤ｒ，并用一个例子显示了这一结果是最好可能的。     

关于轮图优美标号的性质

设G=(V(G)),E(G))为p个顶点,q条边的连通简单图,以x和y为端点的边记作(x,y).定义1 称l为G的一个优美标号,如果l是一个单射:l:V(G)→{0,1,…,q}使得对所有边(x,y)∈E(G),由(?)(x,y)=|l(x)-l(y)|所定义的函数是一个—一对应.并称l(x)为顶点x的优美值.     

生成树与图的结构

在网络研究中,人们需要将图分解为指定的结构,来研究网络的普适性、鲁棒又脆弱性,探索网络进化、动力学复杂性、节点多样性、时空演化复杂性等.生成树与图的结构得到研究,海林图,唯一圈图,具有特殊完美匹配树等图的结构得到刻画.     

Hamilton图的特定生成了图问题的反例

［１］定理３断言：一个Ｈａｍｉｌｔｏｎ图Ｇ必存在仅有ｐ条桥的相间偶圈，如果相间偶圈的边中有边在Ｇ的ｐ个不连通初等子圈上（ｐ≥２）。本的反例表明上述结论是错的，从而［１］中关于Ｐｅｔｅｒｓｏｎ图不是Ｈａｍｉｌｔｏｎ图的证明也不成立。     

二部图生成树的新的计数公式(英文)

设G =(V ,U ,E)是一个连通的二部图 ,其中｜V｜=m ,｜U｜=n .令M (G)表示G的关联矩阵 ,Jk×s 表示元素全为 1的k ×s矩阵 ,R =M (G)M (G)′ , Jm n =Jm -Jm×n-Jn×m Jn,t(G)表示G中生成树的个数 .在本文中我们不用对G的边定向而获得了下面的主要结论 :t(G) =(m n) -2 det( Jm n R) .     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

计算最小支撑出树的一种简便算法

本文通过对网络中有向支撑出树性质的研究,提出了在有向网络图中寻找以某一定点为根的最小有向支撑出树一种较简便的计算方法,并给出了应用该算法进行实际操作的一个算例．     

树上最大支撑森林对策

本文在无向网络上定义了最大支撑森林对策,利用图论知识研究了树上最大支撑森林对策的核和核仁,并将所得结论推广到无关网络上.     

在有向网络中寻找最小支撑入树的计算方法

本文研究了有向网络中支撑入树的性质 ,提出了在有向网络图中寻找以某一指定点为根的最小支撑入树的一种较简便的算法 ,并给出了应用该算法的一个实际算例     

通讯网络中极小费用生成树的一种算法

针对具有n个通讯站的局域网络,运用增加或调整虚设站的方法,给出一种在混合距离下的极小费用生成树的算法.并就MCM91问题B,求出了极小费用生成树,其总费用小于美国马里兰州里斯勃来莱州立大学数学科学系B.A.Fusaro所提供的论文中的费用.     

Optimal Equilibria in the Non-Cooperative Game Associated with Cost Spanning Tree Problems

We study the Pareto optimal equilibria payoffs of the non-cooperative game associated with the cost spanning tree problem. We give two characterisations of these payoffs: one based on the tree they induce and another based on the strategies played by agents. Moreover, an algorithm for computing all these payoffs is provided.     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

On the Minimum Spanning Tree Determined by n Points in the Unit Square

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＡｍｉｎｉｍｕｍｓｐａｎｎｉｎｇｔｒｅｅ（ＭＳＴ）ｉｓｗｉｄｅｌｙａｐｐｌｉｅｄｔｏｔｈｅｆｉｅｌｄｓｏｆｃｏｍｐｕｔｅｒ,ｃｏｍｍｕｎｉｃａｔｉｏｎ,ｎｅｒｗｏｒｋａｎｄｓｏｏｎ．Ｍａｎｙｒｅｓｕｌｔｓｈａｖｅｂｅｅｎｏｂｔａｉｎｅｓ,ｂｕｔｆｅｗｏｆｔｈｅｍｄｅａｌｗｉｔｈｔｈｅｗｏｒｓｔ－ｃａｓｅａｎａｌｙｓｉｓｆｏｒｔｈｅｇｉｖｅｎｆｉｎｉｔｅｒｅｇｉｏｎ．Ｉｎｆａｃｔ,ｉｔｉｓａｍａｘｉｍｉｎｐｒｏｂｌｅｍ（ｓｅｅ［１］——［３］）．Ｔｈｉｓｐａｐｅｒｉ…     

Constrained Inverse Minimum Spanning Tree Problems under the Bottleneck-Type Hamming Distance

In this paper, we consider the inverse minimum spanning tree problem under the bottleneck-type Hamming distance, where the weights of edges can be modified only within given intervals. We further consider the constrained case in which the total modification cost cannot exceed a given upper bound. It is shown that these inverse problems can be transformed into a minimum node cover problem on a bipartite graph, and we give a strongly polynomial time algorithm to solve this type of node cover problems. This work is supported by The National Natural Science Foundation of China (60021201), The Hong Kong Research Grant Council under the grant CERG 9040883 (CITYU 103003), and the Doctoral Foundation of Hohai University (2005-02).     

几类图的支撑树的个数

推广了计算图的支撑树个数的递归公式,解释了组合计数原理的用法.用组合技巧和常系数线性递归序列的解法,对n步梯、n-棱柱、Mobius n-棱柱及有关图,找到了计算它们的支撑树的个数的若干公式.