ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 3, с. 81-84
СИСТЕМНЫЙ АНАЛИЗ =
УДК 519.9
ВЗВЕШЕННЫЕ ГРАФЫ С ФИКСИРОВАННЫМИ СТЕПЕНЯМИ ВЕРШИН И ПОТОКИ В СЕТЯХ*
© 2007 г. А. А. Миронов
Москва, ВЦ РАН Поступила в редакцию 12.10.06 г.
Исследуются классы взвешенных графов (без петель и с петлями), являющиеся реализациями неотрицательных векторов. Множество вершин разбивается на два подмножества и рассматриваются суммы весов ребер на каждом подмножестве и сумма весов ребер, инцидентных вершинам двух подмножеств. Для указанных сумм получены нижние и верхние (достижимые) оценки. Так как разбиение вершин на два подмножества задает разрез сети, а сумма весов ребер, "соединяющих" эти подмножества, есть пропускная способность разреза, то результаты имеют приложение в теории "Потоки в сетях".
Введение. Для неотрицательных вектора и параметра рассматривается класс взвешенных графов (сетей) без петель или с петлями, степени вершин которых равны координатам вектора, а веса ребер и петель не превосходят параметра. Для произвольного разбиения вершин графов этого класса на два подмножества вычисляются нижние и верхние границы сумм весов ребер (и петель) на каждом подмножестве вершин и суммы весов ребер инцидентных этим подмножествам. Исследования основаны на значениях характеристических функций, зависящих от неотрицательных вектора и параметра. Неотрицательность указанных функций - критерий существования рассматриваемых классов взвешенных графов. Статья является продолжением работ [1-3].
Результаты имеют приложения в теории "Потоки в сетях". Разбиение множества вершин сетей класса на два подмножества задает разрез, а сумма весов ребер, инцидентных вершинам этих подмножеств, есть пропускная способность разреза, которая влияет на ограничения при вычислении максимального потока.
1. Характеристические функции и критерии существования с-реализаций вектора в взвешенный граф. Все я-вершинные сети (взвешенные графы) будем рассматривать с фиксированным множеством вершин и (я) = {м1, ..., ип}. Степенью вершины сети называется сумма весов ребер и петли, инцидентных этой вершине. Каждую я-вершинную сеть G будем отождествлять с симметричной матрицей весов ребер и петель С = С^) = {с^ = су(Э): с у > 0, 1 < < i, у < п }, где с,/&) = с,(0) - вес ребра, инцидентного вершинам иг и щ (петли при i = у).
Для множеств векторов введем обозначения: Ш = {А = (а1,..., а) еRn: а >0, 1 < i<я}, Ш = {А е
е Шп : а, > а, + 1, 1 < i < я - 1 (при я > 2)}. Вектор А
г>п
из Шп называется реализуемым в сеть, если существует сеть-реализация G = G(A) такая, что deq щ = а, 1 < г < я. Для сетей-реализаций вектора А е Ш+ запишем, что Г(А) = {G(A)} - множество всех сетей без петель (с,, = 0, 1 < г < я), Г(А) = ^(А)} - множество всех сетей с петлями. Очевидно, что Г/А) Ф
Ф 0 У А е Шп, имеет место [2] теорема.
п
Т е о р е м а 1. Г(А) Ф 0 ^ 2 тах {а1} < X аг.
г = 1
Сети из множеств Г(А; с) = {G = G(A) е Г(А): с^) < с, 1 < г,у < я} и Г,(А; с) = ^ = G(A) еГ(А): Су^) < с, 1 < г, у < я} называются с-реализациями вектора А - с-реализуемым. Здесь определены условия, при которых Г(А; с), Г/А; с) Ф 0. Отметим, что Г(А; 0), Г/А; 0) Ф 0 ^ А - нулевой вектор.
О п р е д е л е н и е 1. Пусть А е Ш+ и с > 0. Характеристическими функциями (ХФ) называются
* Работа выполнена при финансовой поддержке РФФИ (грант < 06-01-00261).
8к( А ;с) = ск( к -1) - X (ск - с - а,) -
г < к а, < ск - с
- X (аг - ск) - X аг п X а,,
г > к г < к г > к
а, > ск
Ак(А;с) = ск2 - X (ск - а,) -
г < к аг < ск
- X ( аг - ск) - X аг + X аг'
(1.1)
(1.2)
г > к аг > ск
г < к г > к
где k е X, 0 < k < п.
Неотрицательность ХФ (1.1) и (1.2) - необходимое условие для Г(А; с) Ф0 и Г/А; с) Ф 0, где А е Ж" [1-3].
Т е о р е м а 2. Если А е Ж", то
а) Г(А; с) Ф 0 ^ 5к(А; с) > 0 Vk, 0 < k < п;
б) Г(А; с) Ф 0 ^ Ак(А; с) > 0 Vk, 0 < k < п.
ХФ (1.1) и (1.2) можно упростить для А е Ж", так как в этом случае одна из сумм при i < k или i > k равна нулю. Справедлива [1-3] следующая лемма.
Л е м м а 1. Если А е Ж" и с > 0, то
а) 5к(А; с) > 0 Vk, 0 < k < (ак + с)/с, ^ 5к(А; с) > 0 Vk, ак+х/с < к < п;
б) Ак(А; с) > 0 Vk, 0 < к < ак/с, ^ Ак(А; с) > 0 Vк, ак+х/с < к < п.
Пусть А е Ж". Упростим ХФ (1.1) и (1.2) для "малых" значений к е X
Ьк (А;с) = ск( к -1) - £( а, - ск) - £ а,- +
г > к а, > ск
г < к
+ £ а- '
г > к
Ак(А ;с) = ск2 - £ (а,- - ск) - £ а,- + £ а
г > к г < к г > к
а > ск
(1.3)
(1.4)
где 0 < к < (ак+с)/с и 0 < к < ак/с соответственно (с > 0).
Неотрицательность ХФ(3) и (4) - критерий существования с-реализаций вектора А е Ж" [1-3].
Т е о р е м а 3. Пусть А е Ж" и с > 0. Тогда
а) Г(А; с) Ф 0 ^ 5к(А; с) > 0 Vk, 0 < к < (ак + с)/с;
б) Г(А; с) Ф 0 ^ Ак(А; с) > 0 Vk, 0 < к < ак/с.
2. Характеристическая функция и критерий существования с-реализации пары векторов в двудольную сеть. Все двудольные сети (взвешенные графы) с долями из п и т вершин будем рассматривать с фиксированными множествами вершин и(п) = {щ, ..., ип} и V(m) = {ух, ..., ут}. Каждой п, т-вершинной сети G поставим в соответствие матрицу весов ребер С = С(О) = {с^ = с^): с,ц > 0, 1 < < i < п, 1 < ц < т}, где сц(3) - вес ребра, инцидентного вершинам щ е и(п) и у е ^т).
ТТ Г>", т
Для множеств пар векторов введем: К+= =
= {(А, В): А е Ж", В е ^, а1 + ... + ап = Ь + ... + Ьт},
Ж+'т = {(А, В): (А, В) е Ж";™, А е Ж", В е ЖТ }. Множество двудольных взвешенных графов-реализаций пары векторов (А, В) е Ж":™ обозначим Г(А, В) = = ^(А, В)}. Очевидно, что Г(А, В) Ф 0 ^А, В) е
е Ж"'™. Сети из множества Г(А, В; с) = {G = G(A, В) е е Г(А, В): с,^) < с, 1 < i < п, 1 <ц < т} называются с-реализациями пары векторов (А, В), а пара (А, В) - с-реализуемой. Отметим, что Г(А, В; 0) Ф Ф 0 ^ А и В - нулевые векторы. Здесь для пары
векторов (А, В) е Ж"'™ и ограничения с определены условия, при которых Г(А, В; с) Ф 0.
О п р е д е л е н и е 2. Пусть (А, В) е Ж"'™, с > 0 и к е X, 1 < к < п. (ХФ) называется
5к(А, В;с) = £ Ь} - £ (Ь; - ск) - £ а,. (2.1)
] < т Ь] > ск % < к
Неотрицательность ХФ (2.1) - необходимое условие для Г(А, В; с) Ф 0 [4-6].
Т е о р е м а 4. Если (А, В) е Ж"'™ , то Г(А, В; с) Ф
Ф 0 ^ 5к(А, В; с) > 0 Vk, 1 < к < п.
При (А, В) е Я",™ неотрицательность ХФ (2.1) -критерий существования с-реализации для (А, В) [4, 5].
Т е о р е м а 5. Если (А, В) е Я"":™, то Г(А, В; с) Ф Ф 0 ^ 5к(А, В; с) > 0 Vk, 0 < к < п.
3. Приведение векторов к с-реализуемости.
Здесь представлены правила, по которым из векторов и пар векторов, не являющихся с-реализуе-мыми, строятся с-реализуемые с наибольшими
суммами координат. Пусть А, О е Ж" и (А, В), (О,
Е) е Ж"+Т. Положим О < А, если 4 < а^г, 1 < , < п,
и (О, Е) < (А, В), если О < А и Е < В. Для А е Ж" и
(А, В) е Я"',™ обозначим Щ(А; с) = {О: О < А, Г(О; с) Ф 0}, Щ(А; с) = {О: О < А, ГЬ(О; с) Ф 0}, Щ(А, В; с) = {(О, Е): (О, Е) < (А, В), Г(О, Е; с) Ф 0}.
Применим ХФ (1.3), (1.4) и (2.1) для построения векторов и пар векторов с указанными выше
свойствами. Допустим А е Ж", (А, В) е Ж"'™. Тогда
5(А;с) =
А( А;с) =
шт 5к(А ;с)
ск < ак" с кУ ' '
Ш<пАк(А;с)
к
Г( А ;с) = 0,
Г( А ;с )Ф0;
Г£( А ;с) = 0, Гь(А;с) Ф 0;
(3.1)
(3.2)
8( А, В ;с) =
Ш<т6к(А, В;с)|' Г(А, В;с) = 0,
I к < 0
Г(А, В;с) Ф 0;
(3.3)
Для А е Ж" и а > 0 пусть Аа= (а
(а)
_,(а)
) -
,(а)
вектор с координатами ау = min(а, а) V,, 1 < , < п и S(A) - сумма координат вектора А. Значения
п
ВЗВЕШЕННЫЕ ГРАФЫ С ФИКСИРОВАННЫМИ СТЕПЕНЯМИ ВЕРШИН
83
(3.1)-(3.3) для A е R+ и (A, B) е R+,= однозначно за дают такие с)), ав(6(А, 5(A) = 5(B))
Т е о р е м а 6. Допустим U(n) = U1 u U2, где U1 n
дают такие числа а(5(А; с)), а(А(А; с)) и аА(5(А, В; п и2 = 0, А = (а1, ., ая) е Я+ и А1 = (а,: щ е и1), А2 = с)), аВ(5(А, В; с)), что соответственно (напомним = (а,: щ е и2), причем 5(А1) < 5(А2). Тогда
а) для VG(A) е Г(А; с) Ф 0 имеет место [7]
_ _а(А А )
8(АЬ А2 1 ;с )< 2 8( и )< ^) --шах((5А1;с), 5(А2, с));
S (А) - 8(A;c) == = S (Аа(8( A ;c))),
S( А) - A( A;c) = = S (Aa(A( A;c))),
S (А) - 8( A, B ;c) = s ( a"a(8( a;c))),
S (B) - 8( A, B;c) = S(BaB (A'B;c)).
_ _а(А А )
S(А2) - S(Ai) + 8(Ai, A2 1 ;c)< 2S(U2)<
(4.2)
Величины (3.1)-(3.3) задают с-реализуемые векторы и пару векторов с наибольшими суммами координат.
Л е м м а 2. Пусть А е Я+ , (А, В) е ВП+'Т и с > 0. Имеет место
а) Г(Аа(5(А;с)); с) Ф 0 и шах 5( Б) = 5(А) - 8(А;
Б е Ж(А;с)
с) [7];
б) ^(Аа(А(А;с)); с) Ф 0 и шах S( Б) = 5(А) -- А(А; с); Б е ж^лс
<S(A2)-max(8(Ai;c), 8(А2, c)); max(8(Ai;c), 8(A2, c)) < 8(Ui, U2) < S(Ai) -
Ta(Ai' A2) 4
- 8( Ai, A2 ;c); б) для VG(A) е rL(A; с) Ф 0 справедливо
_ _a(a A )
8(Ai,A2 " ;c)<28(Ui) + 8l(Ui)<S(Ai)-- max(A(Ai ;c), A(A2, c));
а„(5(A, B;c))
B ; с) Ф i
,) г( Aa a (8( A'B;c))
max S( D) = S(A) - 8(A, B; c).
(D, E) е ЩA, B ;c)
4. Метод характеристических функций при разбиениях сетей на подсети. Подмножества U, V е е U(n), где U n V = 0, и C = {с^ Cj < с Vi, j } - n-вер-шинный взвешенный граф (сеть). Суммы весов ребер и петель на U и V можно представить в виде
8(U) = X cl}, 8(U, V) = £ £ cy
ии4 е U, i < j u4 е Uu; е V
i j ' j i j
_ _а(a A )
S(A2)-S(Ai) + 8(Ai,A2 " ;c)<28(U2) +
(4.3)
8l(U) = X cii,
и, е U
8( u ) = c ■U7'('^i) - 8( u ), 8( u, V) = c|UIV - 8( U, V),
8L(U) = c|U| - 8l( U),
(4.1)
п 5ь( и2) < 5(А2) - шах(А(Аьс), А(А2, с)); шах(А(А1 ;с), А(А2, с)) < 5( и) < 5(А1) -
— —а( А1; А2)
- 5( А1, А2 ;с);
Отметим, что если ар = тах{а,: 1 < г < я}, то Г(А) = = ГL(A;c) при с > ар и Г(А) = Г(А;с) при с > > тах{а,: 1 < < я,, Фр}.
5. Характеристические уравнения и общие свойства с-реализаций. Формулы (4.2) и (4.3), выраженные через значения ХФ (1.3) и (1.4), определяют границы для сумм весов ребер на подмножествах вершин разбиения и (я) = и1 и и2. Однако существуют специальные разбиения множества и (я), при которых ХФ задают точные равенства [1-3, 5, 6].
Пусть Г(А; с) Ф 0 или Г(А; с) Ф 0, где А е Я+ и
рядочиванием координат по невозрастанию (А е k е Z, 0 < k < я. Разобьем множество и(я), поло-
г>п ч тт а г>п п г>ш жив: а) для G(A) е Г(А; с)
е Яп). Для пары векторов А е Яп и В е Яп , где
5(А) < 5(В), вв
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.