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

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

三角形垂心的一个性质

文 [1 ]用解析法发现了三角形外心的一个性质 ,用此法还不难发现三角形垂心的如下性质 :定理　若点 D在△ ABC的边 AB上 ,且∠ CDB =α,O为 C在 AB边所在直线上的射影 H1、H2 、H分别为△ ADC、△ DBC、△ ABC的垂心 ,则( 1 ) | H1H2 | =| AB| . | cotα| ;( 2 ) | H1H | =| OA| . | cot B cotα| ;( 3) | H2 H | =| OB| . | cot A - cotα| .证明　 ( 1 )建如图 1所示的平面直角坐标系 ,设 A( a,0 ) ,D( d,0 ) ,B( b,0 ) ,C( 0 ,c) .过 D点且与 AC垂直的直线方程为y =ac( x - d) .令　 x =0 ,可得y =- adc,故　 H1( 0…     

具有限制的最小 k一个边不交支撑树问题

本文推广了刘振宏等具有次限制最小树算法,给出了求具有限制的最小 k 个边不交支撑树算法.该算法已在 IBM-PC 机上用 Fortran 语言实现,其时间复杂性为max{O(k~2|E|~2|V|~2),O(k~3|V|~4|E|)}.     

综合题新编选登

题 73　 双曲线 x2a2- y2b2 =1(a >0 ,b >0 )的左、右焦点分别为F1,F2 ,点P(x0 ,y0 )是双曲线右支上一点 ,且x0 >2a .I为△PF1F2 的内心 ,直线PI交x轴于Q点 ,若 |F1Q| =|PF2 | ,当a ,b变化时 ,求I分PQ的比λ的取值范围 (见图 1) .解　设双曲线半焦距为c ,则c =a2 +b2 .∵I为PQ的内分点 ,则λ =PIIQ=|PI||IQ| .由内角平分线定理知|PI||IQ| =|PF1||F1Q| =|PF2 ||F2 Q| .又∵ |F1Q| =|PF2 | .∴|PI||IQ| =|PF1||PF2 | ,可得|PI| - |IQ||IQ| =|PF1| - |PF2 ||PF2 | =2a|PF2 | ,|PI||IQ| =|F1Q||F2 Q| ,可得|PI| …     

利用最简几何不等式求最值

几个基本几何不等式如下 :(1)两点间距离最短 ;(2 )三角形两边之和大于第三边 ,两边之差小于第三边 ;(3)点到直线的距离最短 .把这几个基本几何不等式运用到数学中的一些最值问题中 ,将使整个解题过程令人耳目一新 .例 1　如图 1,若 A(3,2 ) ,F为抛物线y2 =2 x的焦点 ,P为抛物线上任意一点 ,求 :| PF| | PA|的最小值 ,以及取得最小值时 P的坐标 .解　由条件可知 ,抛物线的准线 l的方程为 x=- 1.设动点 P(x,y)在准线上的垂足为M(- 1,y) .∵　　 | PF| =| PM| ,∴　要求 | PF| | PA|的最小值 ,即是求 | PM| | PA|的最小值 .如…     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

圆锥曲线定义与范围联用事半功倍

高级中学试验修订本数学第二册 (上 )第八章介绍了圆锥曲线的定义和范围 ,在解决有关问题时 ,若能灵活运用它们 ,则可事半功倍 .例 1　 ( 1 998年希望杯赛题 )Ｅ ,Ｆ是椭圆ｘ24 + ｙ2 =1的左 ,右焦点 ,Ｐ是椭圆上的动点 ,则 |ＰＥ|·|ＰＦ|的最小值是 .解　由椭圆第二定义知 |ＰＥ|·|ＰＦ| =ｅ| ａ2ｃ-ｘＰ|·ｅ| ａ2ｃ+ｘＰ| =|ａ -ｅｘＰ|·|ａ +ｅｘＰ| =|ａ2 -ｅ2 ｘＰ2 | =| 4- 34ｘ2 Ｐ| .由椭圆范围知ｘ2 Ｐ≤ａ2 =4 .∴ |ＰＥ|·|ＰＦ|ｍｉｎ =| 4- 34·4 | =1 .例 2　 ( 2 0 0 2年全国高考题 )点Ｐ( 1 ,0 )到曲线 ｘ =ｔ2ｙ =2ｔ(…     

最小费用k度限制树对策

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

新题征展(63)

A　题组新编1 .( 1 )动点 M( x,y)满足( x - sinα) 2 + ( y - cosα) 2 =| xsinα+ ycosα- 1 | ,判断动点 M的轨迹类型 ;( 2 )动点 M( x,y)满足( x - sinα) 2 + ( y - cosα) 2 =| xsinα+ ycosα- 2 | ,判断动点 M的轨迹类型 ;( 3)动点 M( x,y)满足( x - sinα) 2 + ( y - cosα) 2 =2 | xsinα+ ycosα- 2 | ,判断动点 M的轨迹类型 ;( 4 )动点 M( x,y)满足2 ( x - sinα) 2 + ( y - cosα) 2 =| xsinα+ ycosα- 2 | ,判断动点 M的轨迹类型 .2 .( 1 )过点 P( 1 ,2 )的直线与 x、y轴的正半轴分别交于点 A、B,试求 S△ AOB 的最小…     

函数y=|sinx|的周期问题

对于函数 y =| sinx|的周期 (最小正周期 )问题 ,我们常用图像法来分析 .这里介绍用解析法分析它的周期问题 .由于y =| sinx| =sin2 x =1 - cos2 x2 ,函数值的重复取得 ,等价于 cos2 x值的重复取得 ,故函数的周期为π.例 1　求函数 f( x) =| sinx cosx| ,　 ( x∈ R)的周期 .解　由 f( x) =| sinx cosx|　 =| 2 sin( x π4 ) | =2 sin2 ( x π4 )　 = 1 - cos( 2 x π2 ) ,函数 f ( x)值的重复等价于 cos( 2 x π2 )的值的重复 ,而 cos( 2 x π2 )的周期为π,所以函数 f ( x)的周期为π.例 2　求函数f( x) =1 - cos2 x 1 …     

Some inverse optimization problems under the Hamming distance

Given a feasible solution to a particular combinatorial optimization problem defined on a graph and a cost vector defined on the arcs of the graph, the corresponding inverse problem is to disturb the cost vector such that the feasible solution becomes optimal. The aim is to optimize the difference between the initial cost vector and the disturbed one. This difference can be measured in several ways. We consider the Hamming distance measuring in how many components two vectors are different, where weights are associated to the components. General algorithms for the bottleneck or minimax criterion are described and (after modification) applied to the inverse minimum spanning tree problem, the inverse shortest path tree problem and the linear assignment problem.     

Proof of permutationally convexity of MCSF games

Granot and Huberman (1982) showed that minimum cost spanning tree (MCST) games are permutationally convex (PC). Recently, Rosenthal (1987) gave an extension of MCST games to minimum cost spanning forest (MCSF) games and showed these games have nonempty cores. In this note we show any MCSF game is a PC game.     

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).     

On the inverse problem of minimum spanning tree with partition constraints

In this paper we first discuss the properties of minimum spanning tree and minimum spanning tree with partition constraints. We then concentrate on the inverse problem of minimum spanning tree with partition constraints in which we need to adjust the weights of the edges in a network as less as possible so that a given spanning tree becomes the minimum one among all spanning trees that satisfy the partition restriction. Based on the calculation of maximum cost flow in networks, we propose a strongly polynomial algorithm for solving the problem.The author gratefully acknowledges the partial support of Croucher Foundation.     

Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem

This paper studies heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree using edges that are as similar as possible. Given an undirected labelled connected graph, the minimum labelling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. This problem has been shown to be NP-hard. A Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighbourhood Search (VNS) are proposed in this paper. They are compared with other algorithms recommended in the literature: the Modified Genetic Algorithm and the Pilot Method. Nonparametric statistical tests show that the heuristics based on GRASP and VNS outperform the other algorithms tested. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristics.     

“Optimistic” weighted Shapley rules in minimum cost spanning tree problems

We introduce optimistic weighted Shapley rules in minimum cost spanning tree problems. We define them as the weighted Shapley values of the optimistic game v⁺ introduced in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., forthcoming. The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory. Available from: <http://webs.uvigo.es/gbergant/papers/cstShapley.pdf>]. We prove that they are obligation rules [Tijs, S., Branzei, R., Moretti, S., Norde, H., 2006. Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175, 121–134].     

Connection problems in mountains and monotonic allocation schemes

Directed minimum cost spanning tree problems of a special kind are studied, namely those which show up in considering the problem of connecting units (houses) in mountains with a purifier. For such problems an easy method is described to obtain a minimum cost spanning tree. The related cost sharing problem is tackled by considering the corresponding cooperative cost game with the units as players and also the related connection games, for each unit one. The cores of the connection games have a simple structure and each core element can be extended to a population monotonic allocation scheme (pmas) and also to a bi-monotonic allocation scheme. These pmas-es for the connection games result in pmas-es for the cost game.     

A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.     

On the Biobjective Adjacent Only Quadratic Spanning Tree Problem

The adjacent only quadratic minimum spanning tree problem is an NP-hard version of the minimum spanning tree where the costs of interaction effects between every pair of adjacent edges are included in the objective function. This paper addresses the biobjective version of this problem. A Pareto local search algorithm is proposed. The algorithm is applied to a set of 108 benchmark instances. The results are compared to the optimal Pareto front generated by a branch and bound algorithm, which is a multiobjective adaptation of a well known algorithm for the mono-objective case.     

Minimum Spanning Trees with Sums of Ratios

We present an algorithm for finding a minimum spanning tree where the costs are the sum of two linear ratios. We show how upper and lower bounds may be quickly generated. By associating each ratio value with a new variable in `image space,' we show how to tighten these bounds by optimally solving a sequence of constrained minimum spanning tree problems. The resulting iterative algorithm then finds the globally optimal solution. Two procedures are presented to speed up the basic algorithm. One relies on the structure of the problem to find a locally optimal solution while the other is independent of the problem structure. Both are shown to be effective in reducing the computational effort. Numerical results are presented.