Уравновешенные 2D-разбиения графов
Показано, что для произвольного конечного связного графа с множеством вершин V существует уравновешенное разбиение V=V1 U V2 такое, что ind V1=1, ind V2=2. Рассмотрено и исследовано также два игровых варианта этого утверждения. Показано, що для довільного скінченного зв’язного графа з множиною верши...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84617 |
| 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: | Уравновешенные 2D-разбиения графов / Т.М. Провотар, К.Д. Протасова // Компьютерная математика: сб. науч. тр. — 2011. — № 1. — С. 150-156. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860166340185161728 |
|---|---|
| author | Провотар, Т.М. Протасова, К.Д. |
| author_facet | Провотар, Т.М. Протасова, К.Д. |
| citation_txt | Уравновешенные 2D-разбиения графов / Т.М. Провотар, К.Д. Протасова // Компьютерная математика: сб. науч. тр. — 2011. — № 1. — С. 150-156. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Показано, что для произвольного конечного связного графа с множеством вершин V существует уравновешенное разбиение V=V1 U V2 такое, что ind V1=1, ind V2=2. Рассмотрено и исследовано также два игровых варианта этого утверждения.
Показано, що для довільного скінченного зв’язного графа з множиною вершин V існує врівноважене розбиття V = V1 U V2 таке, що ind V1 = 1, ind V2 = 2. Розглянуто і досліджено також два ігрові варіанти цього твердження.
We show that there is exist a balanced partition V=V1 U V2 for finite connected graphs with the set of vertices V, such that ind V1=1 and ind V2 = 2. We also consider and investigate two game situations of this statement.
|
| first_indexed | 2025-12-07T17:56:41Z |
| format | Article |
| fulltext |
Компьютерная математика. 2011, № 1 150
Òåîðèÿ è ìåòîäû
îïòèìèçàöèè
Показано, что для произвольного
конечного связного графа с мно-
жеством вершин V существует
уравновешенное разбиение V=V1∪
∪V2 такое, что ind V1=1,
ind V2=2. Рассмотрено и исследо-
вано также два игровых вариан-
та этого утверждения.
© T.М. Провотар, К.Д. Протасова,
2011
ÓÄÊ 519.174.1
T.Ì. ÏÐÎÂÎÒÀÐ, Ê.Ä. ÏÐÎÒÀÑÎÂÀ
ÓÐÀÂÍÎÂÅØÅÍÍÛÅ
2-ÐÀÇÁÈÅÍÈß ÃÐÀÔÎÂ
Введение. Все графы, рассматриваемые в
данной работе, считаются связными и неори-
ентированными.
Рассмотрим граф Γ (V,E) с множеством
вершин V и множеством ребер E. Для произ-
вольных двух вершин x,y∈V обозначим d(x,y)
длину кратчайшего пути от x до y. Для про-
извольной вершины x∈V, подмножества A⊆V
и неотрицательного целого числа m обозначим:
B(x,m)={y∈ V: d(x,y) ≤ m},
B(A,m) = ∪ a∈A B(a,m).
Подмножества B(x,m) и B(A,m) называют-
ся шарами радиуса m вокруг вершины x
и подмножества A графа V. Обозначим через
Bm(V) семью всех шаров радиуса m с центра-
ми в вершинах графа.
Непустое подмножество A⊆V имеет ко-
нечный индекс, если найдется такое неотри-
цательное целое число m, что V=B(A,m).
Наименьшее число m, для которого справед-
ливо это равенство, называется индексом
подмножества A и обозначается ind A. Оче-
видно, что ind A ≤ m тогда и только тогда,
когда подмножество A пересекается с каж-
дым шаром из семейства Bm(V).
Уравновешенные разбиения множества
вершин графов
Расстояние Хаусдорфа dist(A, B) между ка-
кими-либо двумя непустыми подмножества-
ми A, B конечного индекса множества вер-
шин V определяется формулой:
УРАВНОВЕШЕННЫЕ 2-РАЗБИЕНИЯ ГРАФОВ
Компьютерная математика. 2011, № 1 151
dist(A, B) = max {max a∈ A min b∈ B d(a,b), max b∈ B min a∈ A d(b, a)}.
Заметим, что ind A=dist(V, A) для произвольного непустого подмножества
A⊆V, а dist (A,B) ≤ ind A, dist(A,B) ≤ ind B.
По определению, разбиение P множества вершин графа Γ (V, E) на Q под-
множеств имеет конечный индекс, если найдется неотрицательное целое число
m, такое что ind PI ≤ m, I∈ {1,..., Q} для всех подмножеств PI разбиения P.
Наименьшее неотрицательное целое число m, для которого выполняются нера-
венства indPI ≤ m, называется индексом разбиения P и обозначается indP. Оче-
видно, что indP≤ k, где k – натуральное число, тогда и только тогда, когда каж-
дое подмножество PI ∈P плотно относительно семейства шаров Bk (V), т. е., каж-
дое подмножество PI пересекается с каждым шаром из Bk (V).
По теореме 1 из [1] (см. также [2, теорема 1.1]) для произвольного конечно-
го графа Γ (V,E) и натурального числа r, |V| ≥ r существует разбиение V=V1∪ V2
∪ ... ∪ Vr такое, что ind Vi ≤ r–1 для всех i ∈ {1,..., r}.
Разбиение X1, X2, ..., Xt, Xt+1 ,... , Xr конечного множества X, |X|=n на r под-
множеств, 1≤ r < n, n=rs+t, 0≤ t <r называют уравновешенным, если
|X1| = |X2|= ... = |Xt| = s+1,
|Xt+1| = |Xt+2| = ... = |Xr|=s.
В случае r| n, имеем
|X1| = |X2| =... = |Xr |.
Для удобства изложения дальнейшего материала перейдем к хроматической
терминологии. Пусть X, C – произвольные множества, |C|=k. Произвольное
сюръективное отображение : X Cχ → : называется k-раскраской множества X
множеством цветов C. Всякая k-раскраска : X Cχ → задает разбиение множе-
ства X на k непустых подмножеств
X = ∪ c∈ C χ–1 (c).
В свою очередь, каждое разбиение множества
X = ∪ α∈ I X α
на непустые подмножества можно отождествить с |I|-раскраской : ,X Cχ →
определенной согласно правилу χ(x) = α тогда и только тогда, когда x∈ Xα.
Т.М. ПРОВОТАР, К.Д. ПРОТАСОВА
152 Компьютерная математика. 2011, № 1
Индексом раскраски χ: V→ C множества вершин графа Γ(V,E) назовем
индекс соответствующего разбиения
V=∪ c∈ C χ–1 (c).
Раскраску χ: X→ {1, 2, …, r} назовем уравновешенной, если соответствую-
щее ей разбиение
X= χ–1 (1)∪ χ–1 (2) ∪ …∪ χ–1 (r)
уравновешено.
Разбиение множества вершин графа Γ(V,E) на r подмножеств имеет индекс,
который не превышает m тогда и только тогда, когда при раскраске
χ: V→ {1, 2, …, r}, соответствующей этому разбиению, каждый шар B(x,m),
x∈ V радиуса m имеет точки всех r цветов. Индексом раскраски называется ин-
декс соответствующего разбиения.
Множество вершин произвольного конечного связного графа, который со-
держит, по крайней мере 2 вершины, можно разбить на два подмножества ин-
декса 1. Но эти разбиения могут оказаться очень неуравновешенными, как пока-
зывает следующий пример.
Рассмотрим дерево Γn (Vn, En), n ≥ 2, где
Vn = {x1, x2, …, xn },
En = {(x1, x2), (x1, x3),…, (x1, xn)}.
Это дерево – звезда. Конечное дерево Γn (V, E), |V|>2 называется звездой с
центром x∈V, если x не является концевой вершиной дерева и любые два крат-
чайших пути от x к различным концевым вершинам не имеют общих ребер.
Существует всего лишь два способа 2-раскраски этого графа – χ1 , χ2 множества
Vn, которые имеют индекс 1, а именно,
χ1 ( x1) = 1,
χ1 ( x2) = χ1 (x3) =...= χ1 ( xn ) = 2;
и
χ2 ( x1) = 2,
χ2 (x2) = χ2 (x3) = ... = χ2 (xn ) = 1.
Если n > 3, то эти раскраски неуравновешенны. Итак, для n > 3 и r = 2 не су-
ществует уравновешенных раскрасок индекса r–1 множества вершин Vn графа
звезды.
Учитывая вышеописанный пример возникает вопрос о существовании урав-
новешенных разбиений в зависимости от их индексов.
УРАВНОВЕШЕННЫЕ 2-РАЗБИЕНИЯ ГРАФОВ
Компьютерная математика. 2011, № 1 153
По теореме 2 из [1] (см. также [2, теорема 1.2]) для произвольного конечного
графа Γ (V, E) и натурального числа r существует уравновешенное разбиение
V=V1∪ V2 ∪ ... ∪ Vr
такое, что
ind Vi ≤ r для всех i ∈ {1, 2, ..., r}.
Согласно теореме 3 из [1] для произвольного конечного графа Γ (V,E) и на-
туральных чисел r, n, где r – делитель n, |V| = n, существует уравновешенное
разбиение
V=V1∪ V2 ∪ ... ∪ Vr
такое, что
dist (V1, V2) ≤ 3, dist (V2, V3) ≤ 3, ..., dist (Vr –1, Vr) ≤ 3, dist (Vr, V1) ≤ 3.
Ряд результатов о разбиении графов методом независимых подмножеств на
подмножества контролируемых индексов дано в [3].
Подмножество S множества вершин V графа Γ называется независимым, ес-
ли S не содержит ни одной пары смежных вершин графа Γ. Существование мак-
симального (за включением) независимого подмножества в конечном графе
очевидно, для того, чтобы построить такое подмножество в бесконечном графе
нужно применить аксиому выбора. Метод независимых подмножеств базируется
на таком утверждении.
По теореме 1 из [3], для произвольного графа Γ(V,E), |V| >1 и Y – максималь-
ное независимое подмножество множества вершин V справедливы утверждения:
1) ind Y = ind (V\Y) =1;
2) для произвольных u,v∈Y существуют y1,..., yn ∈Y такие, что y1 = u, yn = v
и d(yi, yi+1)≤ 3 для всех i∈{1, 2,..., n–1};
3) существует максимальное независимое подмножество Y′ такое, что для
произвольных u,v∈ Y′, найдутся y1, ..., yn ∈ Y′ такие, что y1=u, yn =v и d(yi, yi+1)≤
≤ 2 для всех i∈{1, 2,..., n–1}.
Для дальнейшего изложения результатов дадим некоторые определения.
Радиус rad Γ конечного графа Γ (V, E) определяется формулой
rad Γ = min Vν∈ max x V∈ d(x,v).
По теореме 2 из [3], если rad Γ (V, E) > 2r–1 –1, r – натуральное число, то
множество вершин V можно разбить
V=V1∪ V2 ∪ ... ∪ Vr+1
Т.М. ПРОВОТАР, К.Д. ПРОТАСОВА
154 Компьютерная математика. 2011, № 1
так, что
ind V1 =1, ind V2 ≤ 3, ..., ind Vi ≤ 2i –1,…,
ind Vr ≤ 2r –1, ind Vr+1 ≤ 2r –1.
Напомним, что каждый подграф Γ (V, E′ ) графа Γ (V, E), где E′∈E, называ-
ется его фактором. Фактор связного графа, являющийся связным графом, назы-
вается остовным фактором. Остовый фактор, являющийся деревом, называется
костяком графа или опорным деревом. Под деревом мы понимаем связный граф
без циклов. Дерево Γ (V, E′ ) с выделенным корнем x∈V назовем x-корневым.
Определим частичный порядок ≤ на множестве V по такому правилу: y ≤ z тогда
и только тогда, когда кратчайший путь от x к z проходит через вершину y.
Основной результат данной работы – это усиленный вариант теоремы 2 из
[1], доказанный для r = 2.
Теорема 1. Пусть Γ (V, E) конечный связный граф, |V|=n, n ≥ 2. Тогда су-
ществует уравновешенное разбиение V=V1∪V2 такое, что ind V1 = 1,
ind V2 ≤ 2.
Доказательство. Поскольку при переходе от графа к его опорному дереву
индекс подмножества вершин не уменьшается, можно считать, что наш граф
дерево с корнем x. Покажем, что существует раскраска множества вершин V
двумя цветами, черным и белым, такая, что каждый шар единичного радиуса
содержит хотя бы одну черную вершину, а каждый шар радиуса 2 содержит хотя
бы одну белую вершину.
Применим индукцию по числу вершин n. Для n = 2 теорема очевидна.
Допустим, что мы уже указали соответствующие раскраски для всех деревьев с
числом вершин меньше n.
Обозначим через d расстояние от корня x до самой отдаленной вершины де-
рева. Если d=1, покрасим корень x черным цветом, а остальные вершины произ-
вольно, заботясь лишь о том, чтобы раскраска была уравновешенна.
Допустим, что d >1 и обозначим через xd конечную вершину дерева, для ко-
торой d(x, xd) = d. Если таких вершин несколько, выберем любую из них.
Пусть x = x0, x1,..., xd–2, xd –1, xd – кратчайший путь от корня x до конечной
вершины xd . Удалим ребро (xd–2, xd–1). После этого наше дерево Γ распадается на
два дерева: Γ1 – дерево с корнем x, Γ2 – дерево с корнем xd–1.
К дереву Γ1 применим предположение индукции и раскрасим его уравнове-
шено двумя цветами так, что каждый единичный шар содержит, по крайней ме-
ре, одну черную вершину, а каждый шар радиуса 2 содержит, по крайней мере,
одну белую вершину.
По построению расстояние от корня xd –1 графа Γ2 до какой-либо его верши-
ны, отличной от xd –1, равняется 1. Покрасим вершину xd –1, черным цветом, а вер-
шину xd – белым. Таким образом, мы раскрасили уравновешенно множество
УРАВНОВЕШЕННЫЕ 2-РАЗБИЕНИЯ ГРАФОВ
Компьютерная математика. 2011, № 1 155
вершин графа Γ1 вместе с вершинами xd –1, xd. Продолжим эту раскраску урав-
новешенно на остальные вершины графа Γ.
Доказанная теорема приводит к двум играм между двумя игроками в напе-
ред заданном конечном графе, который имеет, по крайней мере, две вершины.
В каждой из этих игр за первым игроком закрепляется черный цвет, а за вторым
– белый. Далее игроки по очереди красят вершины графа своими цветами.
Заканчиваются игры, когда покрашены все вершины графа.
В первой игре стратегия второго игрока заключается в том, чтобы по окон-
чанию игры множество всех вершин белого цвета имела индекс ≤ 2. Стратегия
первого игрока – помешать второму игроку достичь своей цели.
Теорема 2. Для произвольного графа Γ (V, E) второй игрок имеет выигрыш-
ную стратегию.
Доказательство. Очередной ход второго игрока по выигрышной стратегии
зависит лишь от предыдущего шага первого игрока. Пусть на предыдущем ходу
первый игрок покрасил черным цветом некоторую вершину v. Второй игрок
рассматривает шар B(v, 1). Если в этом шаре имеются неокрашенные вершины,
он выбирает какую-либо из них и красит ее белым цветом. Если в этом шаре по-
крашены все вершины, второй игрок выбирает для раскраски какую-либо вер-
шину из неокрашенных вершин.
Допустим, что, придерживаясь этой стратегии, второй игрок все же проиг-
рал игру. Поскольку подмножество белых вершин, как оказалось, имеет индекс
больше 2, тогда найдется вершина v < V, такая, что все вершины в шаре B(v, 2)
черные. Вершина v покрашена первым игроком на некотором шаге k. Поскольку
второй игрок на k+1 шаге не мог выбрать ни одну вершину в шаре B(v, 1), то все
эти вершины покрашены первым игроком до k-го шага. Возьмем произвольную
вершину u∈ B(v, 1), u≠ v. Она покрашена первым игроком на некотором шаге s,
s < k. Но тогда на (s+4)-м ходу второй игрок обязательно должен был покрасить
одну из вершин в шаре B(u, 1). Таким образом, в шаре B(v, 2) непременно име-
ется, по крайней мере, одна белая вершина, что противоречит нашему предпо-
ложению.
Во второй игре стратегия первого игрока заключается в том, чтобы по окон-
чанию игры множество черных вершин имело индекс 3, а стратегия второго иг-
рока – помешать первому игроку достичь своей цели. В отличие от первой игры,
в этой игре все зависит от игрового поля. Для некоторых графов выигрышную
стратегию имеет первый игрок, для других – второй.
Пример 1. Допустим, что граф имеет две разные вершины u, v, каждая из
которых смежная с конечными вершинами u1, u2 и v1, v2 соответственно. На этом
графе выигрышную стратегию имеет второй игрок. Действительно, пусть на
первом шаге первый игрок покрасил некоторую вершину w. Второй игрок выби-
рает одну из троек u, u1, u2 или v, v1, v2, которые не содержат вершину w. Пусть
для определенности это будет тройка u, u1, u2. Вершина u красится белым цве-
Т.М. ПРОВОТАР, К.Д. ПРОТАСОВА
156 Компьютерная математика. 2011, № 1
том. Следующим шагом второй игрок выбирает одну из вершин u1 или u2, еще
не окрашенных первым игроком. Пусть для определенности это будет вершина
u1. Она красится белым цветом, после чего все вершины в шаре B(u1, 1) белые.
Пример 2. Для графов-отрезков выигрышную стратегию во второй игре име-
ет первый игрок. Действительно, возьмем граф с множеством вершин
{1,2,..., n} и множеством ребер {(1, 2), (2, 3), ..., (n – 1, n)}. На первом шаге пер-
вый игрок красит черным цветом вершину 1. Далее его следующий шаг зависит
от предыдущего шага второго игрока. Если второй игрок перед этим ходом по-
красил белым цветом вершину s, первый игрок рассматривает вершины s–1, s+1.
Если вершина s–1 не покрашена, первый игрок красит ее черным цветом. Если
вершина s–1 уже покрашена, но вершина s+1 не покрашена, тогда красится вер-
шина s+1 черным цветом. Если все три вершины s–1, s, s+1 покрашены, первый
игрок ходит произвольно. Допустим, что, придерживаясь этой стратегии, пер-
вый игрок все же проиграл. Тогда найдутся три последовательные белые верши-
ны s–1, s, s+1. Они покрашены вторым игроком на ходах с некоторыми номера-
ми k1, k2, k3. Следуя описанной стратегии первого игрока, имеем
k1< k2< k3. Но тогда после того, как второй игрок покрасил вершину s, первый
игрок непременно должен был бы покрасить вершину s+1.
Эти размышления приводят к решению такой задачи. На книжной полке
стоят n книжек. Двое друзей выбирают по очереди по одной книжке. Доказать,
что каждый из них имеет такую стратегию выбора, которая не позволяет друго-
му выбрать три книжки, стоящие на полке последовательно.
T.М. Провотар, К.Д. Протасова
ВРІВНОВАЖЕНІ 2-РОЗБИТТЯ ГРАФІВ
Показано, що для довільного скінченного зв’язного графа з множиною вершин V існує врів-
новажене розбиття V = V1∪ V2 таке, що ind V1 = 1, ind V2 = 2. Розглянуто і досліджено також
два ігрові варіанти цього твердження.
T.M. Provotar, K.D. Protasova
BALANCED 2-PARTITIONS OF GRAPHS
We show that there is exist a balanced partition V=V1∪ V2 for finite connected graphs with the set
of vertices V, such that ind V1=1 and ind V2 = 2. We also consider and investigate two game situa-
tions of this statement.
1. Протасова К.Д. Уравновешенные разбиения графов. – М.: Математические заметки. –
2006. –79, № 1б. – С. 127–133.
2. Protasov I., Banakh T. Ball Structures and Colorings of Groups and Graphs. – Lviv: Math.
Stud. Monogr. Ser. V. 11, VNTL, 2003. – 123 р.
3. Провотар Т.М., Протасова К.Д. Розбиття графів методом незалежних підмножин // До-
повіді НАН України, Сер. А, 2010. – № 10. – С. 41–43.
Получено 22.12.2010
Îá àâòîðàõ:
Провотар Татьяна Михайловна,
ведущий инженер Киевского национального университета имени Тараса Шевченко,
УРАВНОВЕШЕННЫЕ 2-РАЗБИЕНИЯ ГРАФОВ
Компьютерная математика. 2011, № 1 157
Протасова Ксения Дмитриевна,
младший научный сотрудник, кандидат физико-математических наук
Киевского национального университета имени Тараса Шевченко.
|
| id | nasplib_isofts_kiev_ua-123456789-84617 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T17:56:41Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Провотар, Т.М. Протасова, К.Д. 2015-07-11T17:08:43Z 2015-07-11T17:08:43Z 2011 Уравновешенные 2D-разбиения графов / Т.М. Провотар, К.Д. Протасова // Компьютерная математика: сб. науч. тр. — 2011. — № 1. — С. 150-156. — Бібліогр.: 3 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84617 519.174.1 Показано, что для произвольного конечного связного графа с множеством вершин V существует уравновешенное разбиение V=V1 U V2 такое, что ind V1=1, ind V2=2. Рассмотрено и исследовано также два игровых варианта этого утверждения. Показано, що для довільного скінченного зв’язного графа з множиною вершин V існує врівноважене розбиття V = V1 U V2 таке, що ind V1 = 1, ind V2 = 2. Розглянуто і досліджено також два ігрові варіанти цього твердження. We show that there is exist a balanced partition V=V1 U V2 for finite connected graphs with the set of vertices V, such that ind V1=1 and ind V2 = 2. We also consider and investigate two game situations of this statement. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Уравновешенные 2D-разбиения графов Врівноважені 2-розбиття графів Balanced 2-partitions of graphs Article published earlier |
| spellingShingle | Уравновешенные 2D-разбиения графов Провотар, Т.М. Протасова, К.Д. Теория и методы оптимизации |
| title | Уравновешенные 2D-разбиения графов |
| title_alt | Врівноважені 2-розбиття графів Balanced 2-partitions of graphs |
| title_full | Уравновешенные 2D-разбиения графов |
| title_fullStr | Уравновешенные 2D-разбиения графов |
| title_full_unstemmed | Уравновешенные 2D-разбиения графов |
| title_short | Уравновешенные 2D-разбиения графов |
| title_sort | уравновешенные 2d-разбиения графов |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84617 |
| work_keys_str_mv | AT provotartm uravnovešennye2drazbieniâgrafov AT protasovakd uravnovešennye2drazbieniâgrafov AT provotartm vrívnovažení2rozbittâgrafív AT protasovakd vrívnovažení2rozbittâgrafív AT provotartm balanced2partitionsofgraphs AT protasovakd balanced2partitionsofgraphs |