Рассматриваются классы неориентированных сетей с фиксированными степенями узлов. Построен аппарат для исследования таких классов, основанный на следующем. При произвольном разбиении множества узлов на два подмножества переменными величинами являются: суммы весов дуг на каждом подмножестве и сумма весов дуг, инцидентных двум подмножествам. Для этих переменных получены достижимые нижние и верхние границы, как в случае ограничения весов дуг общей кон-стантой и степенями узлов, так и в случае ограничения весов дуг только степенями узлов. Этот ап-парат применим в теории "Потоки в сетях", рассматривая сети как ориентированные с симметрич-ной матрицей пропускных способностей дуг. Например, для двухполюсной сети из класса рассмат-риваемых сетей получена минимальная величина максимального потока, а также ограничение максимальной величины максимального потока. Аналогичная проблема решена и в случае, когда любой узел есть исток или сток. Указанный аппарат также позволяет строить сети с максимальной плотностью весов дуг на выделенном подмножестве узлов.
展开▼
