Об одной верхней оценке для взвешенного числа устойчивости графа
We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on th...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2007 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84998 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859946121778954240 |
|---|---|
| author | Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| author_facet | Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| citation_txt | Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on the polytope CSTAB(G) , and it is also an exact upper bound for the weighted stability number of the t-perfect graph.
|
| first_indexed | 2025-12-07T16:13:37Z |
| format | Article |
| fulltext |
80 Теорія оптимальних рішень. 2007, № 6
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Для взвешенного числа устойчи-
вости неориентированного гра-
фа G выведена верхняя оценка,
которая является решением зада-
чи линейного программирования с
числом ограничений 3(| | )O V , где
V – количество вершин в графе.
Доказано, что полученная верхняя
оценка не хуже, чем известная
оценка, связанная с многогранни-
ком ( )CSTAB G , а также являет-
ся точной оценкой сверху для
взвешенного числа устойчивости
t -совершенного графа.
П.И. Стецюк, C.И. Бутенко,
О.А. Березовский, 2007
ÓÄÊ 519.8
Ï.È. ÑÒÅÖÞÊ, C.È. ÁÓÒÅÍÊÎ, Î.À. ÁÅÐÅÇÎÂÑÊÈÉ
ÎÁ ÎÄÍÎÉ ÂÅÐÕÍÅÉ ÎÖÅÍÊÅ
ÄËß ÂÇÂÅØÅÍÍÎÃÎ ×ÈÑËÀ
ÓÑÒÎÉ×ÈÂÎÑÒÈ ÃÐÀÔÀ∗∗∗∗
Введение. Пусть ( , )G V E= – взвешенный
неориентированный граф с множеством вер-
шин V и множеством ребер E ; вес каждой
вершины i V∈ задан положительным целым
числом
i
w . Подмножество вершин S V⊆
называется устойчивым (или независимым)
множеством графа G , если для любых
,i j S∈ ребро ( , )i j не принадлежит E .
Взвешенное число устойчивости графа G
определяется как ( , ) max
i
i S
G w w
∈
α = ∑ , где
S V⊆ – устойчивое множество. Множество
*
S , на котором достигается ( , )G wα , назы-
вается максимальным взвешенным устойчи-
вым (или независимым) множеством.
В общем случае задача нахождения
взвешенного числа устойчивости графа G
NP-трудная. Доказано [1], что она является
NP-трудной даже в частном случае, когда все
веса вершин равны единице. Поэтому актуа-
лен поиск оценок, приближающих как взве-
шенное число устойчивости графа ( , )G wα ,
так и обычное число устойчивости графа
( )Gα , когда все веса вершин графа равны
единице. Величина ( )Gα характеризует
мощность максимального по числу вершин
устойчивого множества графа G .
∗
Работа выполнена при финансовой поддерж-
ке гранта UKM2-2812-KV-06 (CRDF Cooperative
Grants Programm).
ОБ ОДНОЙ ВЕРХНЕЙ ОЦЕНКЕ ДЛЯ ВЗВЕШЕННОГО ЧИСЛА УСТОЙЧИВОСТИ ГРАФА
Теорія оптимальних рішень. 2007, № 6 81
Пусть
Sχ – "инцидентный" вектор для подмножества S V⊆ :
| |S VRχ ∈ ,
1S
i
χ = , если i S∈ , 0S
i
χ = , если \i V S∈ . Выпуклая оболочка "инцидентных"
векторов
Sχ для всех устойчивых множеств S графа G
( ) : { : - устойчивое множество}SSTAB G conv S V= χ ⊆
называется многогранником устойчивых множеств (stable set polytope) [2]. Тогда
задача нахождения взвешенного числа устойчивости графа G формулируется
следующим образом:
( , ) max , ( ).
i i
i V
G w w x x STAB G
∈
α = ∈∑ (1)
В общем случае многогранник устойчивых множеств ( )STAB G может иметь
очень сложную структуру [2], чем обусловлено то, что задача нахождения
( , )G wα является NP -трудной. Вычисление "тесных" верхних оценок для
( , )G wα , которые достаточно хорошо аппроксимируют сверху значение целе-
вой функции в задаче (1), имеет как практический, так и теоретический интерес.
Расcмотрим верхнюю оценку, связанную с многогранником:
2 1
2 1
0 1 для каждой вершины ,
( ) 1 для каждого ребра ( , ) ,
для каждого нечетного цикла ,
k
i
i j
i k
i C
x i V
CSTAB G x x i j E
x k C V
+
+
∈
≤ ≤ ∈
= + ≤ ∈
≤ ∈
∑
который аппроксимирует (сверху) многогранник устойчивых множеств
( )STAB G . Условимся эту оценку обозначать
* ( , )
C
G wα . Для ее нахождения
требуется решить задачу линейного программирования (ЛП-задачу):
* ( , ) max , ( ),
C i i
i V
G w w x x CSTAB G
∈
α = ∈∑ (2)
которая в общем случае содержит неполиномиальное количество ограничений.
Несмотря на это, задача (2) разрешима за полиномиальное время [2]. Полиноми-
альный алгоритм для нахождения
* ( , )
C
G wα базируется на использовании мето-
да эллипсоидов и на том, что если точка x удовлетворяет первым двум семей-
ствам линейных неравенств для многогранника ( )CSTAB G , то за полиномиаль-
ное время можно либо убедиться, что точка x удовлетворяет ограничениям для
всех нечетных циклов, либо найти нечетный цикл, для которого ограничение
будет максимально нарушаться. Для этого требуется найти | |V кратчайших пу-
тей в специально построенном неориентированном графе G′ , содержащем
2 | |V вершин (вершины V и их копии V ′ ) и 2 | |E ребер.
П.И. СТЕЦЮК, C.И. БУТЕНКО, О.А. БЕРЕЗОВСКИЙ
82 Теорія оптимальних рішень. 2007, № 6
t -совершенными ( t -perfect) графами называют семейство графов, для кото-
рых многогранник устойчивых множеств ( )STAB G совпадает с многогранни-
ком ( )CSTAB G ( ( ) ( )STAB G CSTAB G= ). Для t -совершенных графов оценка
* ( , )
C
G wα является точной оценкой сверху для ( , )G wα , т.е. справедливо сле-
дующее равенство:
* ( , ) ( , ).
C
G w G wα = α (3)
Естественно, что когда граф G принадлежит семейству t -совершенных графов,
то задача (1) полиномиально разрешима в том смысле, что ( , )G wα может быть
найдено с любой заданной точностью за полиномиальное время.
Многогранник ( )CSTAB G можно описать с помощью полиномиального ко-
личества линейных ограничений [3, с. 1187], используя переменные
ij
y для каж-
дого ребра ( , )i j E∈ и переменные ,u v
z для каждой пары вершин ,u v V∈ . Об-
ласть действия ограничений, связанных с нечетным циклом, эквивалентна сле-
дующей системе линейных ограничений:
.
,
, ,
1 для каждого ребра ( , ) ,
1 для каждой вершины ,
для каждого ребра ( , ) ,
для всех , , , : ( , ), ( , ) .
ij i j
v v
u v uv
t w t v uv vw
y x x i j E
z v V
z y u v E
z z y y t u v w V u v v w E
= − − ∈
≥ ∈
≤ ∈
≤ + + ∈ ∈
(4)
Таким образом, для t -совершенных графов ( , )G wα может быть найдено за по-
линомиальное время с помощью любого из полиномиальных алгоритмов для
задачи линейного программирования. Заметим, что результирующее количество
ограничений для описания многогранника ( )CSTAB G с помощью (4), равно
2(| | | |)O V E .
Рассмотрим оценку
* ( , )G w∆α , нахождению которой соответствует ЛП-задача
с полиномиальным количеством ограничений (порядка
3| |V ). Покажем, что
оценка
* ( , )G w∆α не менее точная оценка сверху для ( , )G wα , чем оценка
* ( , )
C
G wα . Естественно, что оценка
* ( , )G w∆α также будет точной верхней
оценкой для ( , )G wα , когда граф G является t -совершенным.
Вывод оценки
* ( , )G w∆α . ЛП-задача для оценки
* ( , )G w∆α следует релакса-
цией (ослаблением) определенной формулировки квадратичной булевой задачи,
с помощью которой формулируется проблема нахождения ( , )G wα . Построение
ЛП-задачи опишем последовательностью этапов, которые будем комментиро-
ОБ ОДНОЙ ВЕРХНЕЙ ОЦЕНКЕ ДЛЯ ВЗВЕШЕННОГО ЧИСЛА УСТОЙЧИВОСТИ ГРАФА
Теорія оптимальних рішень. 2007, № 6 83
вать необходимыми сведениями.
Этап 1. Рассмотрим задачу о максимальном взвешенном устойчивом множе-
стве графа G в виде следующей квадратичной булевой задачи [4]:
( , ) max
i i
i V
G w w x
∈
α = ∑ (5)
при ограничениях
0 ( , ) ,
i j
x x i j E= ∀ ∈ (6)
2 0 ,
i i
x x i V− = ∀ ∈ (7)
где булевая переменная {0,1}
i
x ∈ равна единице, если вершина i включается в
устойчивое множество, и равна нулю – иначе. Булевые переменные описаны
квадратичными ограничениями равенствами (7). Квадратичные ограничения (6)
означают, что если две вершины связаны ребром в графе G , то они обе не могут
одновременно принадлежать независимому множеству.
Этап 2. Переформулируем задачу (5)–(7) с помощью бинарных ( 1± )-пере-
менных:
1 2 ,
i i
y x i V= − ∀ ∈ (8)
где вершине i соответствует бинарная переменная
i
y , которая равна 1− , если
вершина i включается в устойчивое множество, и равна 1 в противном случае.
В результате получаем квадратичную задачу для бинарных переменных в сле-
дующей формулировке:
( , ) max
2 2
i i i
i V
w w y
G w
∈
α = −
∑ (9)
при ограничениях
1 0 ( , ) ,
i j i j
y y y y i j E− − + = ∀ ∈ (10)
2 1 .
i
y i V= ∀ ∈ (11)
Этап 3. Добавим к задаче (9)–(11) семейство квадратичных ограничений:
1,
1,
, , : .
1,
1,
i j i k j k
i j i k j k
i j i k j k
i j i k j k
y y y y y y
y y y y y y
i j k V i j k
y y y y y y
y y y y y y
+ + + ≥ −
− − + ≥ −
∀ ∈ < <
− + − ≥ −
+ − − ≥ −
(12)
Ограничения (12) не изменяют множества оптимальных решений задачи
(9)–(11) [5]. Они следуют из того, что для произвольной тройки бинарных
( 1± )-переменных
i
y ,
j
y и
k
y , такой что i j k≠ ≠ всегда правильными явля-
ются квадратичные ограничения в виде неравенств
П.И. СТЕЦЮК, C.И. БУТЕНКО, О.А. БЕРЕЗОВСКИЙ
84 Теорія оптимальних рішень. 2007, № 6
2
2
2
2
( ) 1,
( ) 1,
( ) 1,
( ) 1.
i j k
i j k
i j k
i j k
y y y
y y y
y y y
y y y
+ + + ≥
− + + ≥
+ − + ≥
+ + − ≥
Последние легко преобразовываются к форме (12), учитывая, что
2 1
i
y = ,
2 1jy = и
2 1
k
y = .
Этап 4. Линеаризуем задачу (9)–(12), положив
ij i j
y y y= для каждой пары
,i j V∈ , таких что i j< и релаксируя ограничения (11) линейными неравенст-
вами 1 1
i
y i V− ≤ ≤ ∀ ∈ . В результате получаем ЛП-задачу
* ( , ) max
2 2
i i i
i V
w w y
G w∆
∈
α = −
∑ (13)
при ограничениях
1 0 ( , ) ,
ij i j
y y y i j E− − + = ∀ ∈ (14)
1 1 ,
i
y i V− ≤ ≤ ∀ ∈ (15)
1,
1,
, , : .
1,
1,
i j ik j k
i j ik j k
i j ik j k
i j ik j k
y y y
y y y
i j k V i j k
y y y
y y y
+ + + ≥ −
− − + ≥ −
∀ ∈ < <
− + − ≥ −
+ − − ≥ −
(16)
Учитывая, что ЛП-задача (13)–(16) получена ''ослаблением'' квадратичной за-
дачи (9)–(12), имеем
* ( , ) ( , ).G w G w∆α ≥ α (17)
Следовательно, оценка * ( , )G w∆α есть оценкой сверху для взвешенного числа
устойчивости ( , )G wα .
Этап 5. Переформулируем задачу (9)–(12) с помощью ''релаксированных'' бу-
левых переменных. Для этого ''релаксированные'' бинарные переменные
,
i
y i V∈ переведем в ''релаксированные'' булевые переменные с помощью заме-
ны (8), а ''релаксированные'' бинарные переменные
ij
y – в ''релаксированные''
булевые переменные
ij
x с помощью замены
1 2 , : .
ij ij
y x i j V i j= − ∀ ∈ < (18)
В результате получаем, что оценке
* ( , )G w∆α соответствует ЛП-задача
ОБ ОДНОЙ ВЕРХНЕЙ ОЦЕНКЕ ДЛЯ ВЗВЕШЕННОГО ЧИСЛА УСТОЙЧИВОСТИ ГРАФА
Теорія оптимальних рішень. 2007, № 6 85
* ( , ) max
i i
i V
G w w x∆
∈
α = ∑ (19)
при ограничениях
0 ( , ) ,
i j ij
x x x i j E+ − = ∀ ∈ (20)
2,
0,
, , : .
0,
0;
ij ik jk
ij ik jk
ij ik jk
ij ik jk
x x x
x x x
i j k V i j k
x x x
x x x
+ + + ≤
− − + ≤
∀ ∈ < <
− + − ≤
+ − − ≤
(21)
0 1 .
i
x i V≤ ≤ ∀ ∈ (22)
ЛП-задача (19)–(22) содержит 3(| | )O V ограничений. Точное количество ог-
раничений равно | | 2 | | 2 | | (| | 1)(| | 2) / 3E V V V V+ + − − . Из них самую значи-
тельную часть, равную 2 | | (| | 1)(| | 2) / 3V V V− − , определяют ограничения
(21), которые (а также их форма в бинарных переменных) известны как ограни-
чения треугольника (triangle inequalities). Их наличие придает ЛП-задаче (19)–
(22) интересные "геометрические" свойства, связанные с нечетным циклом
2 1k
C + в графе G .
Свойства оценки
* ( , )G w∆α . Справедлива следующая теорема.
Теорема 1. Из ограничений (20) и (21) следует справедливость линейных не-
равенств
2 1k
i
i C
x k
+∈
≤∑ (23)
для каждого нечетного цикла 2 1k
С V+ ∈ .
Доказательство. Рассмотрим произвольный нечетный цикл 2 1k
C + с верши-
нами 1 2 1{ , , }
k
i i +K и ребрами 1 1 2 1( , ), 1, , 2 , ( , )
r r k
i i r k i i+ += K . Не ограничивая
общности, будем считать что 1 2 2 1k
i i i +< < <K . Для цикла 2 1k
C + ограничения
(20) имеют следующий вид:
1 1 1 2 1 1 2 1
, 1, 2, , 2 , ,
r r r r k ki i i i i i i i
x x x r k x x x
+ + + +
+ = = + =K
и сложив их получим
1 2 1 1
2 2 2
1 1
2 .
r k r r
k k
i i i i i
r r
x x x
+ +
+
= =
= +∑ ∑ (24)
Оценим правую часть в равенстве (24).
Если 1k = (соответствует нечетному циклу 3C ), то для тройки вершин
( 1 2 3, ,i i i ) из первого неравенства в (21) следует справедливость неравенства
1 2 1 3 2 3
2.
i i i i i i
x x x+ + ≤
П.И. СТЕЦЮК, C.И. БУТЕНКО, О.А. БЕРЕЗОВСКИЙ
86 Теорія оптимальних рішень. 2007, № 6
Тогда из равенства (24) имеем
1 3 1 1 2 1 3 2 3
3 2
1 1
2 2,
r r ri i i i i i i i i i i
r r
x x x x x x
+
= =
= + = + + ≤∑ ∑
откуда следует
3
3
1
1 или 1,
ri i
r i C
x x
= ∈
≤ ≤∑ ∑
что дает доказательство теоремы для нечетного цикла 3C .
Пусть k – произвольное натуральное число, такое что 2k ≥ . Рассмотрим
"покрытие" вершин нечетного цикла 2 1k
C + двумя типами треугольников (трой-
ками вершин), которое для цикла 9C показано на рисунке.
РИСУНОК. Покрытие треугольниками вершин нечетного цикла 9C
Для первого типа треугольников ("незаштрихованные") будем использовать
первое неравенство из (21), а для второго типа треугольников ("заштрихован-
ные") – третье неравенство из (21).
Первый тип треугольников содержит следующие тройки вершин:
1 2 3 2 1 2 2 1( , , ), , ( , , )
k k k
i i i i i i− +K . Количество таких троек равно k , и из первого не-
равенства в (21) для них следует справедливость неравенств
2 1 2 2 1 2 1 2 2 1
2, 1, , .
t t t t t ti i i i i i
x x x t k
− − + +
+ + ≤ = K
Сложив их, получаем
2 1 2 2 1 2 1 2 2 1
1 1 1
2
t t t t t t
k k k
i i i i i i
t t t
x x x k
− − + +
= = =
+ + ≤∑ ∑ ∑ .
Затем запишем в виде
ОБ ОДНОЙ ВЕРХНЕЙ ОЦЕНКЕ ДЛЯ ВЗВЕШЕННОГО ЧИСЛА УСТОЙЧИВОСТИ ГРАФА
Теорія оптимальних рішень. 2007, № 6 87
1 3 2 1 2 1 2 1 2 2 2 1
2 1 1
2 .
t t t t t t
k k k
i i i i i i i i
t t t
x x x x k
− + − +
= = =
+ + + ≤∑ ∑ ∑ (25)
Второй тип треугольников содержит следующие тройки вершин:
1 3 5 1 2 1 2 1( , , ), , ( , , )
k k
i i i i i i− +K . Количество таких троек равно ( 1)k − , и из третьего
неравенства в (21) для них следует справедливость неравенств
1 2 1 1 2 1 2 1 2 1
0, 2, , ,
t t t ti i i i i i
x x x t k
− + − +
− + − ≤ = K
сложив которые получаем неравенство
1 3 1 2 1 2 1 2 1
2
0.
k t t
k
i i i i i i
t
x x x
+ − +
=
− + − ≤∑
Сложив последнее неравенство с неравенством (25), получаем неравенство
1 2 1 2 1 2 2 2 1
1 1
2 .
k t t t t
k k
i i i i i i
t t
x x x k
+ − +
= =
+ + ≤∑ ∑ (26)
Учитывая, что
2 2 1 2 1 2 2 1 2 2 2 1 1
2
1 1 1 1
( ) ,
t t t t t t t t r r
k k k k
i i i i i i i i i i
t t t r
x x x x x
+ − − + +
= = = =
+ = + =∑ ∑ ∑ ∑
из неравенства (26) имеем справедливость неравенства
1 2 1 1
2
1
2 .
k r r
k
i i i i
r
x x k
+ +
=
+ ≤∑ (27)
Далее, подставляя (27) в (24), получаем
1 2 1 1
2 1 2
1 1
2 2 ,
r k r r
k k
i i i i i
r r
x x x k
+ +
+
= =
= + ≤∑ ∑
откуда следует неравенство
2 1
2 1
1
или ,
r
k
k
i i
r i C
x k x k
+
+
= ∈
≤ ≤∑ ∑
что завершает доказательство теоремы.
Перейдем к исследованию свойств оценки
* ( , )G w∆α . Cправедлива следую-
щая теорема.
Теорема 2. Для произвольного графа G оценка
* ( , )G w∆α удовлетворяет со-
отношению
* *( , ) ( , ) ( , ).
C
G w G w G w∆α ≥ α ≥ α
Доказательство. Из определения оценки
* ( , )G w∆α следует, что
* ( , ) ( , )G w G w∆α ≥ α (см. формулу (17)). Докажем, что
* *( , ) ( , )
C
G w G w∆α ≥ α . От
задачи (19)–(22) легко перейти к ЛП-задаче:
П.И. СТЕЦЮК, C.И. БУТЕНКО, О.А. БЕРЕЗОВСКИЙ
88 Теорія оптимальних рішень. 2007, № 6
* ( , ) max
i i
i V
G w w x∆
∈
α = ∑ (28)
при ограничениях
0 ( , ) ,
i j ij
x x x i j E+ − = ∀ ∈ (29)
2,
0,
, , : .
0,
0;
ij ik jk
ij ik jk
ij ik jk
ij ik jk
x x x
x x x
i j k V i j k
x x x
x x x
+ + + ≤
− − + ≤
∀ ∈ < <
− + − ≤
+ − − ≤
(30)
0 1 ,
i
x i V≤ ≤ ∀ ∈ (31)
1 ( , ) ,
ij
x i j E≤ ∀ ∈ (32)
1 ( , ) ,
i j
x x i j E+ ≤ ∀ ∈ (33)
2 1
2 1 .
k
i k
i C
x k C V
+
+
∈
≤ ∀ ∈∑ (34)
Здесь дополнительные ограничения (32) получены из ограничений (30). Так, на-
пример, сложив первое и последнее из неравенств (30), имеем 2 2
ij
x ≤ , откуда
следует справедливость неравенств (32). Ограничения (33) получены в результа-
те сложения ограничений (29) с ограничениями (32). Ограничения (34) связаны с
нечетными циклами в графе G и следуют из теоремы 1.
Задача (28)–(34) включает избыточные линейные ограничения (32)–(34), ко-
торые следуют из ограничений (29)–(31). От задачи (28)–(34) перейдем к
''ослабленной'' ЛП-задаче, убрав из нее все ограничения за исключением ограни-
чений (31), (33) и (34). В результате получаем ЛП-задачу
* ( , ) max
i i
i V
G w w x
∈
α = ∑ (35)
при ограничениях
0 1 ,
i
x i V≤ ≤ ∀ ∈ (36)
1 ( , ) ,
i j
x x i j E+ ≤ ∀ ∈ (37)
2 1
2 1 ,
k
i k
i C
x k C V
+
+
∈
≤ ∀ ∈∑ (38)
для которой
* *( , ) ( , )G w G w∆α ≥ α . Задача (35)–(38) является формулировкой
задачи (2) для нахождения
* ( , )
C
G wα , так как ограничения (36)–(38) – определе-
ние многогранника ( )CSTAB G , т.е.
* *( , ) ( , )
C
G w G wα = α . Отсюда имеем
* *( , ) ( , )
C
G w G w∆α ≥ α . Теорема доказана.
ОБ ОДНОЙ ВЕРХНЕЙ ОЦЕНКЕ ДЛЯ ВЗВЕШЕННОГО ЧИСЛА УСТОЙЧИВОСТИ ГРАФА
Теорія оптимальних рішень. 2007, № 6 89
Из теоремы 2 и равенства (3), которое означает что для t -совершенных гра-
фов оценка
* ( , )
C
G wα является точной оценкой сверху для ( , )G wα , следует
справедливость теоремы
Теорема 3. Если граф G – t -совершенный, то
* ( , ) ( , )G w G w∆α = α .
Следовательно, для t -совершенных графов оценка
* ( , )G w∆α точная верхняя
оценка для взвешенного числа устойчивости ( , )G wα .
П.І.Стецюк,C.І. Бутенко,О.А. Березовський
ПРО ОДНУ ВЕРХНЮ ОЦІНКУ ДЛЯ ЗВАЖЕНОГО ЧИСЛА СТІЙКОСТІ ГРАФА
Для зваженого числа стійкості неорієнтованого графа G виведено верхню оцінку, яка є
розв’язком задачі лінійного програмування з числом обмежень 3(| | )O V , де V – кількість
вершин в графі. Доведено, що отримана верхня оцінка не гірша за відому оцінку, що
пов’язана з багатокутником ( )CSTAB G , а також є точною оцінкою зверху для зваженого чи-
сла стійкості t -перфектного графа.
P.I. Stetsyuk,S.I. Butenko,O.A. Berezovski
ON ONE UPPER BOUND FOR THE WEIGHTED STABILITY NUMBER OF A GRAPH
We derived an upper bound for the weighted stability number of a simple undirected graph G ,
which is the solution of a linear pogramming problem with 3(| | )O V constraints, where V is a
number of vertices in the graph. We proved that this upper bound is at least as good as the known
bound based on the polytope ( )CSTAB G , and it is also an exact upper bound for the weighted
stability number of the t -perfect graph.
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.:
Мир, 1982. – 416 с.
2. Grotschel M., Lovasz L., Schrijver A. Geometric Algorithms and Combinatorial Optimiza-
tion. – Berlin: Springer-Verlag, 1988. – 362 p.
3. Schrijver A. Combinatorial Optimization: Polyhedra and Efficiency. – Berlin: Springer,
2003. – 1881 p.
4. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Dordrecht: Kluw-
er, 1998. – 394 p.
5. Стецюк П.И. Новые модели квадратичного типа для задачи о максимальном взве-
шенном разрезе графа // Кибернетика и системный анализ. – 2006. – №1. – C. 63–75.
Получено 17.04.2007
|
| id | nasplib_isofts_kiev_ua-123456789-84998 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T16:13:37Z |
| publishDate | 2007 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.И. Бутенко, С.И. Березовский, О.А. 2015-07-18T06:16:34Z 2015-07-18T06:16:34Z 2007 Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84998 519.8 We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on the polytope CSTAB(G) , and it is also an exact upper bound for the weighted stability number of the t-perfect graph. Работа выполнена при финансовой поддержке гранта UKM2-2812-KV-06 (CRDF Cooperative Grants Programm). ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об одной верхней оценке для взвешенного числа устойчивости графа On one upper bound for the weighted stability number of a graph Article published earlier |
| spellingShingle | Об одной верхней оценке для взвешенного числа устойчивости графа Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| title | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_alt | On one upper bound for the weighted stability number of a graph |
| title_full | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_fullStr | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_full_unstemmed | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_short | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_sort | об одной верхней оценке для взвешенного числа устойчивости графа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84998 |
| work_keys_str_mv | AT stecûkpi obodnoiverhneiocenkedlâvzvešennogočislaustoičivostigrafa AT butenkosi obodnoiverhneiocenkedlâvzvešennogočislaustoičivostigrafa AT berezovskiioa obodnoiverhneiocenkedlâvzvešennogočislaustoičivostigrafa AT stecûkpi ononeupperboundfortheweightedstabilitynumberofagraph AT butenkosi ononeupperboundfortheweightedstabilitynumberofagraph AT berezovskiioa ononeupperboundfortheweightedstabilitynumberofagraph |