ON THE BOTTLENECK CAPACITY EXPANSION PROBLEMS ON NETWORKS

This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G(V, A, C) consisting of a set of nodes V= {v1,v2,…,vn},a set of arcs A ■ {(vi, vj) | i=1,2,…, n;j=1,2,…,n} and a capacity vector C. The component cij of C is the capacity of arc (vi ,vj). Define the capacity of a subset A' of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc (vi, vj) is wij. In the node-expanding model, it is assumed that the capacities of all arcs (vi,vj) which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems (path, spanning arborescence and maximum flow) in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.     

“点评者”的情怀——例谈数学教师的点评艺术

《义务教育数学课程标准(2011年版)》关于"课程基本理念"下第3点即指出:"教学活动是师生积极参与、交往互动、共同发展的过程,有效的教学活动是学生学与教师教的统一,学生是学习的主体,教师是学习的     

我的《排列》教学的心路历程

1背景揭示《排列》(第一课时)这节课,作为最近我省优质课评比、省教坛新星评比的考评课课题之一,引起了一线数学教师的广泛关注.参评者见仁见智,观摩者众说纷纭.作为上述两项活动的评委,对本节课自然有更多的感慨.这次作为省特级教师讲师团成员赴皖北讲学活动中,在确定所执教的课题时,首先想到的是《排列》     

赋模糊权的拟强连通有向网络中的最佳树形图

本文在赋模糊数为弧权的拟强连通有向网络中，建立了根据模糊决策来求解最佳树形图的网络模型，并给出了这一模型的有效算法。     

一类较为广泛的概率中考题

纵观2010年的概率中考试题,用列举法求概率已成为出现较为广泛的一类概率命题,现将列举法求概率的知识进行梳理并结合中考题给予解析.一、列举法求概率知识的梳理1.列举法求概率的前提是问题应为古典概率问题,即当一次试验中出现的各种可能结果     

求第K棵树形图的算法

本文利用拟阵交的交错序列思想，并借助改进的求第ｋ最短路的算法，给出了求第ｋ最小树形图的算法，时间复杂度为Ｏ（ｋ３｜Ａ｜３）．     

生产函数构成的树形图分析方法

作为生产函数几何表示的尝试，本文通过对生产函数要素构成的分析，归纳出一种用树形图表示生产函数的方法，这种方法直观形象，能清晰地表示各要素之间的结构关系和指标关系．     

Oriented tree diagram Lie algebras and their abelian ideals

We introduce oriented tree diagram Lie algebras which are generalized from Xu＇s both upward and downward tree diagram Lie algebras, and study certain numerical invariants of these algebras related to abelian ideals.