最小树的层次算法及全部最小树动态结构

最小树问题在国民经济中有着广泛的应用。本文提出不同于著名的kruskal算法[1]及其他算法的层次算法,并推导出揭示最小树不变量的枝杈确定性以及边可作为最小树树枝的充要条件,最后得出全部最小树的动态结构。由于实际选用最小树时还经常需要兼顾其它具体     

最小树图的Hamilton性及全部最小树的生成

对给定的连通图G,树图T(G)的Hamilton性,首先由Cummins所证明。稍后,Kamae给出另一构造证明,并用于树的生成。本文将研究一个赋权图G所有最小树的一些性质。主要结果如下:(1)对任意赋权图G,证明了最小树图T_(min)(G)的Hamilton性;(2)根据构造性证明,给出生成全部最小树的算法。     

最小树的一般算法

本文根据设计并行算法的基本原则,给出了最小树的两个对偶定理.在此基础上,建立了两种对偶的同步并行算法的雏型.这两种算法恰恰在对偶的意义下,概括了以往的最小树算法.     

关于Steiner最小树问题

在本刊第二卷第二期上,我们曾发表了黄光明的《最短网络》一文,对Steiner最小树问题在当时的发展情况作了一些介绍。最近由于他与堵丁柱共同解决了Gilbert和Pallak在1968年所提出的一个猜想,不少读者对于这一问题产生了兴趣。为此,我们组写了这篇文章,目的在于使读者对这一问题的历史和连带产生的问题以及目前的发展状况有一较确切的和较全面的了解。     

相对于Wiener-Hosoya指标的最小树

Wiener-Hosoya指标是由Randic在文[1]中引入的一个指标,旨在揭示分子结构与其化学性质的更进一步的关系.任意给定点数及直径,本文确定了相对于该指标的最小树.进一步地,具有任意给定点数的最小的16个树也得到确定.     

最小树问题的全部解

<正> 以某些实际问题(如管道设计、通讯网建设等)为背景,图论中的最小树问题引起人们的广泛兴趣.自从 Kruskal 提出三种基本的构造法以后,各种算法实现途径相继出现,使这一问题得到完满的解决.然而,实际问题往往不能满足于求出一个最小树,而希望兼顾其它目标,在若干最小树中进行再选择.这就要求我们讨论最小树问题的全部解.在已有文献中,求全部支撑树已有较成熟的算法,尤其是文献[4]提供的算法可以将全部支撑树按权的大小依次列出.从理论上说,可以认为这些结果已经包含了求全部最小树问题.作为另一种途径,本文将着重讨论最小树问题全部解的性质,并由此建立求全部解的广探法(求全部支撑树的 Mayeda-Seshu 算法的推广).     

正多边形上的最大点

设有正n(n≥3)边形A1…An,其中Ai的坐标为(xi,yi),i=1,…,n,对正n边形上任一点X(x,y),记f(X)=n∑i=1XAi=n∑i=1√(x-xi)2 (y-yi)2=f(x,y) (1)     

无向图上最小树的唯一性定理

本文研究各边具非负长度的有限无向图中最小树的唯一性,得到下述定理:H为图G上唯一最小树的充要条件是对任一不属于H之边e,图H∪{e}所含之唯一圈中,e是唯一最长边. 给定无向图G=(X,U),X为顶点集合,U为边集合,对边e∈U,给定长度l(e)≥     

求最小树的破圈法

§1.引言 最小树问题是图论中一个有较广泛实际应用的问题,它的提法如下: 设G-(X,U)是一个有限无向图,这里X表示图G的顶点的集合,U表示G的边的集合.我们设G是连通的,即对于G的任意两个不同的点x_i与x_j,都存在一条由U的边组成的链把x_i与x_j连接起来(关于图论的一些基本概念的较详细的叙述,可以参看[1]).     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

具有次限制的最小树问题

F.Glover和D.Klingman在[2]中给出了予先确定的一个点x具有固定次数为k的最小树算法。 本文给出了任意m个互不关联点具有次数限制的最小树问题的算法.算法的基础是线性规划的对偶理论。     

网络最小树的一种矩阵算法

求网络最小树问题，人们熟知常用的方法有“避圈法”和“破圈法”，这些方法有其直观易解的优点，然而它们毕竟是要在图上作业（在图上完成）。由于网络与距离矩阵的对应关系，本文将利用矩阵性质给出该问题的一个矩阵解法。     

特殊图形上的顶点坐标

例1(2010年湖北武汉)如图1,所有正方形的中心均在坐标原点,且各边与x轴或y轴平行,从内到外,它们的边长依次为2,4,6,8,…,顶点依次用A1,A2,A3,A4…表示,则顶点A55的坐标为     

复平面上正多边形的判定及应用

结合教学给出复平面上n个点成为正多边形的条件,最后讨论它的一些应用.     

具有顶点与边限制的最大基数对集

简单图G=[V,E],任意给定SV,FE。求G的最大基数对集,Edmonds给出了著名的花算法[1]。我们首先利用修改算法[2],求复盖S中尽可能多的顶点的最大基数对集。当然,这样的对集可能还不是唯一的;在所有这样的对集中,我们要找一个对集,使得它进一步满足新增加的条件——使得|M∩|F|的基数最小。本文给出了这一问题的一个算法。算法的主要步骤是: ①利用改进的花算法[2],在G中找复盖S中尽可能多的顶点的最大基数对集,从而得     

顶点在一组平行线上的正三角形

<正>2013年北京市海淀区一模22题是一道很好的题,将正方形、三角形放入一组平行线中,使各顶点分别落在平行线上,画图并计算,探究性强,背景新颖.其中最后一问直接写出正三角形的边长,思维含量很高且不易直接写出,有一定的难度.笔者为此进行了一题多解,以发散同学们的思维,开阔视野.     

连通图中过指定顶点集的圈的存在性

图论中的一个重要问题是Hamilton圈的存在性问题.由于一般的Hamilton图的充要条件难于获得,故一些作者便退一步在某些给定类型的图中寻求长度尽可能大的圈.例如,Dirac即证明了2-连通图中存在着经过某一指定顶点集N(u)UN(v)U{u,v}的圈,从而得到了如下的定理(可参看[3]的介绍): 定理A.设G是个n阶的2-连通图,P是G中的一条最长路,u及v是P的两端点,d(u)+d(v)=f.若4≤f相似文献   

正多边形的一个充要条件

正多边形的一个充要条件赵小云（杭州大学数学系３１００２８）１９８７年第２２届ＩＭＯ中有这样一个预选题：证明，如果等边凸五边形ＡＢＣＤＥ的各个角满足：那么它是一个正五边形．这个问题的解，我们可以通过计算和比较图形中边角关系的大小来完成．如图１．取ＡＣ中...     

正多边形的一个性质

文[1]给出了“正三角形各顶点到其外接圆上任意一点的切线的距离之和为定值”这一结论的推广.本文将其推广到一般情形. 引理 设自然数n≥3,a为实常数,记