ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 5, с. 28-37
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.9
МЕТОД ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЙ ДЛЯ КЛАССОВ СЕТЕЙ С ФИКСИРОВАННЫМИ СТЕПЕНЯМИ УЗЛОВ*
© 2014 г. П. С. Селин, В. И. Цурков
Япония, Акита, Университет Акита Россия, Москва, ВЦ РАН Поступила в редакцию 10.04.14 г., после доработки 29.04.14 г.
Исследуются классы сетей с фиксированными степенями узлов и с непревосходящими заданного параметра весами (пропускными способностями) дуг и петель. Приведены характеристические функции, зависящие от координат вектора и параметра, неотрицательность которых есть критерий существования сети, степени ее узлов равны координатам вектора, а веса дуг не превосходят параметра. Множества узлов сетей указанных классов разбиваются на два подмножества. Переменными являются суммы весов дуг на каждом подмножестве и сумма весов дуг, инцидентных узлам двух подмножеств. Получены формулы, задающие оценки снизу и сверху для указанных переменных. Результаты имеют приложение для вычисления потоков в сетях, так как разбиение узлов определяет разрез сети.
БО1: 10.7868/80002338814050126
Введение. В работе рассматриваются классы неориентированных сетей с фиксированными степенями узлов (вершин), веса дуг (ребер) которых не превосходят заданного параметра. Под сетью понимаются взвешенные графы. Произвольное разбиение множества узлов сети на два подмножества задает две подсети, порожденные этими подмножествами, и двудольную подсеть. В [1, 2] исследовались классы сетей без петель, для которых были получены (достижимые) оценки снизу и сверху для сумм весов дуг подсетей разбиения. Здесь построены эти же оценки для классов сетей с петлями. Конструкции основаны на характеристических функциях и уравнениях: неотрицательность характеристической функции — это критерий существования сети с заданными степенями узлов и заданным ограничением для весов (пропускных способностей) дуг; характеристические уравнения при специальных разбиениях множества узлов сетей рассматриваемого класса точными равенствами для сумм весов дуг на подмножествах узлов определяют общие свойства сетей класса.
Сумма весов дуг двудольной подсети разбиения множества узлов — это величина пропускной способности разреза сети. Поэтому полученные результаты имеют приложение теории потоков в сетях (величина максимального потока сети равна минимальной пропускной способности разреза [3]). Оценки для сумм весов дуг и петель на подмножествах узлов разбиения применимы для построения сетей с максимальной или минимальной плотностью весов дуг и петель на указанных подмножествах.
1. Основные определения. Все я-вершинные сети будем рассматривать с фиксированным множеством узлов и(п) = Щь..., ип}. Степень узла — это сумма весов дуг и петли, инцидентных узлу. Обозначим через
= {А = (аь..., ап): а1 > 0, г = 1,п}
множество я-координатных неотрицательных векторов. Вектор A из К + называется реализуемым в сеть, если существует сеть О = О(А) такая, что deg щ = а1 VI. Сеть О^) — реализация вектора A. Каждая я-вершинная сеть О взаимно-однозначно соответствует весовой функции дуг С = (Су),
Су > 0,1, у = 1, п, где Су — вес дуги, инцидентной узлам Ы1 и Щц (петли при I = ц) сети О. Поэтому сеть О^) будем отождествлять с весовой функцией дуг
* Работа выполнена при финансовой поддержке РФФИ (грант № 13-01-00866).
С(Л) = |с<, : at = degu = £ с.., vj. (1.1)
Будем предполагать, что вектор Л е [R + формирует множество сетей с петлями
Г¿(Л) = {С(Л) : С(Л) удовлетворяет (1.1)}. Множество сетей без петель, реализаций вектора A, обозначим
Г(Л) = {С(Л) 6 Г¿(Л) : с„ = 0V/}(Г(Л) с Г¿(Л)). Будем также рассматривать множества сетей с ограничением сверху весов дуг: для c > 0 положим Г ¿(Л; с) = {С(Л) е Г ¿(Л) : cy < сУ1, j}, Г(Л;с) = {С(Л) е Г(Л): су < сУ1, j}.
Отметим, что Г ¿(Л; с) = Г ¿(Л) при с > max aj, а в случае Г(Л) Ф 0 имеет место: если ap = max aj, то
_ i
Г(Л; с) = Г(Л) при с > max{a, : j = 1, n,i Ф p}.
В статье построен аппарат исследования сетей из Г(Л; с) и Г ¿(Л; с). Пусть U(n) = U1 u U2, U1 n U 2 = 0 — разбиение множества узлов. В данной работе для множеств сетей из Г(Л; с), Г ¿(Л; с),
где Л е , построены оценки снизу и сверху для сумм весов дуг и петель подсетей, порожденных U1 и U2 и двудольной сети с долями U1 и U2.
Пусть Л е [+. Очевидно, что Г ¿(Л) Ф 0, а для Г(А) имеет место [4]: если ap = max al, то
i
Г(Л) Ф 0 ^ 2ap < a1 + ... + an.
2. Критерии с-реализуемости в сеть. Не ограничивая общности, будем рассматривать векторы, координаты которых упорядочены по невозрастанию:
= {А е Я+ : щ > а+ъ1 = 1,п - 1 (при п > 2)}. Определение 1. Для А е [+, с > 0 и к е {р е Ж : р > 1} величины
8 к (А; с) = ск(к - 1) - ^ (щ - ск) - ^ щ + ^ щ, ск < йк + с, (2Л)
¡> к +1 К к ¡> к +1
щ > ск
А к (А; с) = ск + 8 к (А; с), ск < ик, (2.2)
называются характеристическими функциями (ХФ) [4—6].
Неотрицательность ХФ (2.1) и (2.2) — это критерии с -реализуемости вектора [4—6].
Те о р е м а 1. Пусть А е и с > 0. Тогда:
а) Г(А; с) Ф 0 ^ 8 к (А; с) > 0, У к е {к : к > 1, ск < ик + с};
б) Г 1(А; с) Ф 0 ^ А к (А; с) > 0, У к е {к : к > 1, ск < ик}.
При разбиении множества узлов сети на два подмножества образуется двудольная сеть. Для исследования двудольных сетей введем обозначение
= {(Л,B): Л 6 B 6 С, a + ... + an = b + ... + bm}.
Все n, ш-вершинные двудольные сети будем рассматривать с фиксированными долями U(n) = {м1, ..., un} и V(m) = {v1, ..., vm}. Каждая n, ш-вершинная двудольная сеть G взаимно однозначно соответствует весовой функции дуг С = (су), су > 0, j = 1,n, j = 1,m, где Су — вес дуги, инцидентной узлам ui и Vj. Для пары векторов (Л, B) е [ +'m через Г(Л, B) обозначим множество двудольных сетей-реализаций пары (A, B), для которых deg Uj = aj, j = 1, n, deg Vj = by, j = 1, m:
{m n I
С(Л,B) = (с(У) : a j = ^ j = 1,n,bj = ^ с v, j = 1,ml.
Очевидно, что Г(А, В) Ф 0У(А, В) е К+'т. При с > 0 положим
Г(А, В;с) = {С(А, В) = (су) : Сц < с V/,у}. Обозначим
Ж+т= = {(А, В) е Яп;т= : А е Щ, В е Я+т}
Определение 2. Для (А, В) е К+'т и к е Ж, с > 0 величина
т к
5к(А, В;с) = £ Ьц - £ (Ьц - ск) - £ а„ к е Ж, (2.3)
ц = 1 Ьц > ск I = 1
к = 1, п, называется ХФ [7—13].
Неотрицательность ХФ (2.3) — это критерий с-реализуемости пары векторов в двудольную сеть [7—13].
Те о р е м а 2. Если (А,В) е К+т и с > 0, то Г(А,В;с) Ф 0 о 8к(А,В;с) > 0, Vк к = Щ.
3. Характеристические уравнения. Пусть С(А) е Г ¿(А; с), где А е К + и О, Т с и (п), Q п Т = 0. Введем обозначения для сумм весов дуг и петель:
5(О) = £ ц 5¿(О) = £ с,, 5(О) = МЬ1-5(О),
щ, Щц е О и/ е О
/ < ц
Ъь(О) = с|О| - 8¿(О), 8(О,Т) = £ сц, 8(О,Т) = с|О||Т| - 8(О,Т).
Щ- е О
иц е Т
Построим соотношения, связывающие суммы весов дуг и петель на подмножествах узлов специальных разбиений множества Щ(я) со значениями ХФ (2.1)—(2.3).
Определение 3. Пусть А е К + и с > 0. Для V к, 1 < к < — + 1, ^-разбиением множества уз-
с
лов и(я) относительно вектора A и параметра с называется представление и(п) = и1к и и2 и и3к, где и1 = {щ- : / < к}, и2 = {щ : / > к,а{ > ск}, и3к = {щ- : / > к,а{ < ск}. Справедливо утверждение [8—13].
Те о р е м а 3. Пусть А е К+, (А,В) е К , с > 0 и к е Ж, к = \п. Тогда:
а) если Г(А; с) ^ 0, то V С (А) е Г(А; с) имеет место
28(ик) + 8(и1,и2к) + 8(и2,и3) + 28(и3) = 8к(А;с), ск < а^ + с; (3.1)
б) если Г ¿(А; с) ^ 0, то УС(А) е Г ¿(А; с) имеет место
28(и1) + Ъ1(и1к) + 8(и1, иЧ) + 8(и2к, и3) + 8ь{икъ) + 28^) = Ак(А;с), ск < а^; (3.2)
в) при Г(А, В; с) Ф 0 V С (А, В) е Г(А, В; с) справедливо
8({щ : / < k},{vц : Ьц > ск}) + 8({щ : / > к},{^ : Ьц < ск}) = 8к(А,В;с). (3.3)
Определение 4. Соотношения (3.1)—(3.3) называются характеристическими уравнениями для множеств Г(А; с), Г ¿(А; с), Г(А, В; с).
Характеристические уравнения задают "жесткость" для сумм весов дуг (и петель) подсетей, порожденных ^-разбиениями Щ(я). В частности, из равенства нулю значений ХФ следует равенство нулю всех слагаемых в (3.1)—(3.3), что будет применяться в последующих конструкциях.
4. Приведение векторов к с-реализуемости с наибольшей суммой координат. Введем понятие вписанности векторов и пар векторов.
Определение 5. Пусть Л, D е . Вектор D называется вписанным в A, (D < Л), если dt < aj V j j = 1, n. Пусть (Л, B), (D, E) e [+'m. Пара векторов (D, E) называется вписанной в (A, B) ((D,E) < (Л,B)), если D < Л и E < B.
Обозначим:
Ш(Л; с) = {D : D < Л,T(D; с) * 0}
и
ML(K с) = {D : D < Л,Г¿(D; с) ф 0}
— множества c-реализуемых векторов, вписанных в A;
Ш(Л, B; с) = {(D, E) : (D, E) < (Л, B),r(D, E; с) * 0}
— множество c-реализуемых пар векторов, вписанных в (A, B). Для произвольных вектора и пары векторов будут найдены c-реализуемые векторы и пара векторов с наибольшими суммами координат, вписанные в заданные. Это даст возможность для множества сетей c-реализаций заданного вектора при любом разбиении множества узлов на два подмножества установить нижние и верхние оценки сумм весов дуг (и петель) подсетей, порожденных этим разбиением.
Пусть Л е [ + и (Л, B) е [ +'m. Для ХФ (2.1)—(2.3) введем обозначения:
5( Л; с) = jlT^ с)1, Г(Л; с) = 0, (4.1)
10, Г(Л; с)*0;
А(А ) iN*Ak(Л; с)|, rz(Л; с) = 0,
А (Л; с) = Л k I (4.2)
10, rz(Л; с)*0;
i IminSk(Л, B; с)|, Г(Л, B; с) = 0,
5(Л, B; с) = Л k kV ' ' Т v ' ' 7 ' (4.3)
10, Г(Л, B; с)*0.
Легко проверить, что
n
5(Л; 0) = Д(Л; 0) = 5(Л; B;0) = V at.
j = 1
Величины (4.1)—(4.3) представляют собой минимальные значения, на которые необходимо уменьшить суммы координат векторов для получения с-реализуемых.
Лемма 1. Пусть Л е [+, (Л,B) е и с > 0. Тогда:
n n
а) max V dt = V at - 5(Л;с);
D е Ш(Л;с)
б) max V d( = V aj - А(Л; с);
D е Ш ¿(Л;с)
А j = 1 j = 1
n n
в) max V di = V aj - 5(Л, B;с).
(D,E) e Ш(A,B;c) . _ . _ 1
Пункты а) и в) доказаны в [1]. Пункт б) будет следовать из лемм 2—6. Приведем ХФ (2.2) к следующему виду:
k
Ak(Л;с) = ск1к(Л;с) - V at + V at, (4.4)
j = 1 j > k^)
lmax{j : at > ck}, ak+1 > ck, где/k (Л; с) = -!
[k, ak+1 < ck.
Для (2.1)—(2.3) и (4.4) также будем пользоваться сокращенными обозначениями: дк (А; с) = дк, Ак (А; с) = Ак,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.