Аннотация
Classes of networks (weighted graphs) with fixed degrees of vertices are investigated. For these classes, networks are constructed in which the sum of the maximum weight of a network edge and the maximum weights of the edges of all vertices is a minimum. In particular, under the constraints used in transport models, for the set of matrix-plans of the transport problem, an algorithm which finds the matrix of this set of which the sum of its largest element and the largest elements of every row and column is a minimum is constructed. A criterion is suggested under which the orders of vertices of a certain network or a bichromatic network, with weights of edges not greater than a fixed positive number, are equal to prescribed non-negative numbers.
Ключевые слова
weighted graphs;fixed degrees of vertices; maximum weight of a network edge; transport models; bichromatic network
|
