最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

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

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

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

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

一类最小支撑树的逆问题及其求解方法

本文针对传统的基于边的最小支撑树逆问题，提出了一类基于点边更新策略的最小支撑树逆问题．更新一个点是指减少与此点相关联的某些边的权值．根据是否含有更新点的费用，考虑了两类模型，它们均可转化为森林上的最小(费用)点覆盖的求解问题，算法的复杂性都是O(mn)，其中m=|E|n=|V|。     

图的局部k限制边连通性及最优性

首先研究图的局部k限制边连通性问题和局部λ_k-连通图的存在性问题.然后研究图的局部λ_k最优性,并且应用邻域条件得到了一个保证图局部λ_k最优的充分条件.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

一种基于Split-findmin和Set-maxima的最小支撑树灵敏度分析方法

本文首先根据最小支撑树的截性质和圈性质给出了灵敏度分析的基本公式,然后基于现代图论算法中经典的Split—findmian数据结构介绍了树上边的灵敏度分析算法,最后将非树边的灵敏度分析转化为已有成熟的算法的Set—maxima问题进行处理.     

瓶颈型Hamming距离下约束最小支撑树的反问题

本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小. 把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法.     

关于具有最大路长限制的顺序二分树

本文给出了一个构造具有最大路长限制的最小价格顺序二分树的算法;引进了分界数的概念。并证明了关于分界数的基本定理,从而使算法的计算量同O(n~2L)成比例,文中还讨论了具有最大路长限制的Huffman树问题,给出相应的算法,计算量也为O(n²L)。     

最小加权费用树问题

本文在赋顶点权θ的无向网络中,建立了最小加权费用树问题的网络模型,对问题的复杂性给出了证明并给出了求解该问题的算法。     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．     

具有最小反对称分割指数的化学树

设图$G$,其中边集为$E(G)$,顶点集$V(G)$.反对称分割指数被定义为$ISDD(G)=\sum_{uv \in E(G)}\dfrac{d_ud_v}{d_u^2+d_v^2}$,其中$d_u$, $d_v$分别为顶点$u,v$的度.化学树就是顶点的度不超过4的树.在本文中,我们刻画出具有最小反对称分割指数的$n$阶化学树.     

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

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

最小支撑树博弈:重新审视Bird配置

最小支撑树博弈是合作博弈中的经典模型,自1973年被Claus和Kleitman提出后持续得到学术界关注.最小支撑树博弈不仅跟图论和组合优化中的最小支撑树问题一脉相承,还在水网、电网和公路铁路网建设中的成本分摊问题中有重要应用. Bird配置因其简洁性和直观性持续受到大量关注,是最小支撑树博弈最著名的求解方案.本文基于Edmonds对最小支撑树问题的线性规划表示,利用对偶定理给出Bird配置一种新的等价公式.本文还研究了最小支撑树博弈的一种推广,即点加权的最小支撑树博弈,并证明了Bird配置的一个变形依然在这个推广博弈的核中.     

关于拟阵的最小限制基问题

关于求拟阵的最小基问题,众所周知,有很简明的算法(被称为Greedy Algorithm)。本文考虑求带剖分限制的最小基问题,同样也给出了较简单的有效算法,最后举例说明,许多组合问题都可以化成拟阵的最小限制基问题而求解。     

关于具有最大路长限制的顺序扩充二分树

本文是文献[3]的继续,文中研究了具有转移函数和价格函数的L-限制扩充顺序二分树,关于模型1和模型2最优解的同一性定理(定理1)是建立递推公式和定义分界数的理论根据,为解决带有一类转移函数的L-限制顺序扩充分树问题奠定了基础,主要结果是分界数的三个定理(定理2—4)。     

两个不交图的联图的最小圈基长度

这篇文章中,我们分两种情形分别给出了计算两个不交图的联图的最小圈基长度的公式.作为它们的应用,我们给出了计算n个相同的图的联图以及完全r-部图等图的最小圈基长度的公式.     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.