Розбиття графів методом незалежних підмножин
Запропоновано метод незалежних підмножин, що дозволяє побудувати вершинні розбиття графів з контрольованими індексами підмножин розбиття.
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2010
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/30720 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Розбиття графів методом незалежних підмножин / T.M. Провотар, K.Д. Протасова // Доп. НАН України. — 2010. — № 10. — С. 41-43. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-30720 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-307202012-02-12T12:37:49Z Розбиття графів методом незалежних підмножин Провотар, T.M. Протасова, K.Д. Інформатика та кібернетика Запропоновано метод незалежних підмножин, що дозволяє побудувати вершинні розбиття графів з контрольованими індексами підмножин розбиття. We present a method of independent subsets for vertex partitions of graphs into subsets of controlled indices. The index of a subset A of the set V of vertices of a graph Γ is the minimal number k such that, for every vertex v that belongs V, there exists a path of length ≤k from v to A. 2010 Article Розбиття графів методом незалежних підмножин / T.M. Провотар, K.Д. Протасова // Доп. НАН України. — 2010. — № 10. — С. 41-43. — Бібліогр.: 10 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/30720 519.112 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Провотар, T.M. Протасова, K.Д. Розбиття графів методом незалежних підмножин Доповіді НАН України |
| description |
Запропоновано метод незалежних підмножин, що дозволяє побудувати вершинні розбиття графів з контрольованими індексами підмножин розбиття. |
| format |
Article |
| author |
Провотар, T.M. Протасова, K.Д. |
| author_facet |
Провотар, T.M. Протасова, K.Д. |
| author_sort |
Провотар, T.M. |
| title |
Розбиття графів методом незалежних підмножин |
| title_short |
Розбиття графів методом незалежних підмножин |
| title_full |
Розбиття графів методом незалежних підмножин |
| title_fullStr |
Розбиття графів методом незалежних підмножин |
| title_full_unstemmed |
Розбиття графів методом незалежних підмножин |
| title_sort |
розбиття графів методом незалежних підмножин |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2010 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/30720 |
| citation_txt |
Розбиття графів методом незалежних підмножин / T.M. Провотар, K.Д. Протасова // Доп. НАН України. — 2010. — № 10. — С. 41-43. — Бібліогр.: 10 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT provotartm rozbittâgrafívmetodomnezaležnihpídmnožin AT protasovakd rozbittâgrafívmetodomnezaležnihpídmnožin |
| first_indexed |
2025-07-03T11:06:42Z |
| last_indexed |
2025-07-03T11:06:42Z |
| _version_ |
1836623648957399040 |
| fulltext |
УДК 519.112
© 2010
T.M. Провотар, K. Д. Протасова
Розбиття графiв методом незалежних пiдмножин
(Представлено членом-кореспондентом НАН України С. I. Ляшком)
Запропоновано метод незалежних пiдмножин, що дозволяє побудувати вершиннi роз-
биття графiв з контрольованими iндексами пiдмножин розбиття.
Нехай Γ(V,E) — зв’язний граф з множиною вершин V i множиною ребер E. Для довiльних
вершин x, y ∈ V позначимо через d(x, y) довжину найкоротшого шляху вiд x до y. Для
довiльних вершини x ∈ V , пiдмножини A ⊆ V та невiд’ємного цiлого числа m позначимо
B(x,m) = {y ∈ V : d(x, y) 6 m}, B(A,m) =
⋃
a∈A
B(a,m).
Пiдмножини B(x,m) та B(A,m) називаються кулями радiусом m навколо x та A.
За означенням, пiдмножина A ⊆ V має скiнченний iндекс, якщо знайдеться таке не-
вiд’ємне цiле число m, що V = B(A,m). Найменше невiд’ємне цiле число m, для якого
справедлива ця рiвнiсть, називається iндексом пiдмножини A i позначається indA.
За теоремою 1 з [1] (див. також [2, теорема 1.1]), для довiльних скiнченного графа
Γ = Γ(V,E) та натурального числа r, |V | > r iснує розбиття V = V1
⋃
V2
⋃
· · ·
⋃
Vr таке, що
indVi 6 r − 1 для кожного i ∈ {1, . . . , r}.
Розбиття скiнченної множини X, |X| = n на r пiдмножин, 1 6 r < n, n = rs + t,
0 6 t < r називають врiвноваженим, якщо
|X1| = |X2| = · · · = |Xt| = s+ 1, |Xt+1| = |Xt+2| = · · · = |Xr| = s.
У випадку r|n ми маємо |X1| = |X2| = · · · = |Xr|.
За теоремою 2 з [1] (див. також [2, теорема 1.2]), для довiльного скiнченного графа
Γ(V,E) та натурального числа r iснує врiвноважене розбиття V = V1
⋃
V2
⋃
· · ·
⋃
Vr таке,
що indVi 6 r для кожного i ∈ {1, 2, . . . , r}.
Для натурального числа k граф Γ(V,E) називається k-регулярним, якщо |B(x, 1)| = k+1
для кожної вершини x ∈ V . k-Регулярний граф Γ(V,E) називається калейдоскопiчним, якщо
iснує розфарбування χ : V −→ {0, 1, . . . , k} множини вершин V k + 1-м кольором таке, що
кожна куля B(x, 1) радiусом 1 не має двох однокольорових вершин. Розфарбування χ задає
розбиття V = χ−1(0)
⋃
χ−1(1)
⋃
· · ·
⋃
χ−1(k) i indχ−1(i) = 1 для кожного i ∈ {0, 1, . . . , k}.
Якщо граф Γ(V,E) скiнченний, то χ−1(0) = χ−1(1) = · · · = χ−1(k). Таким чином, калей-
доскопiчнi графи оптимальнi щодо врiвноважених розбиттiв. Про калейдоскопiчнi графи
див. [2, гл. 3], [3–5], деякi варiацiї калейдоскопiчних графiв розглянуто в [6–8].
Пiдмножина S множини вершин V графа Γ(V,E) називається незалежною, якщо
d(u, v) > 1 для всiх u, v ∈ S. Iснування максимальної (за включенням) незалежної множини
у скiнченному графi очевидне, а для того щоб побудувати таку множину у нескiнченному
графi, можна використати аксиому вибору.
Метод незалежних пiдмножин базується на такому твердженнi.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №10 41
Теорема 1. Нехай Γ(V,E) є граф, |V | > 1, Y — максимальна незалежна пiдмножи-
на V . Тодi
1) indY = ind(V \ Y ) = 1;
2) для довiльних u, v ∈ Y iснують y1, . . . , yn ∈ Y такi, що y1 = u, yn = v i d(yi, yi+1) 6 3
для кожного i ∈ {1, 2, . . . , n − 1};
3) iснує максимальна незалежна пiдмножина Y ′ така, що для довiльних u, v ∈ Y ′
знайдуться y1, . . . , yn ∈ Y ′ такi, що y1 = u, yn = v i d(yi, yi+1) 6 2 для кожного i ∈
∈ {1, 2, . . . , n − 1}.
За теоремою Турана [9], для кожного скiнченного графа Γ(V,E) iснує незалежна пiд-
множина S ⊂ V така, що |S| >
∑
v∈V
|B(v, 1)|−1. Було б цiкаво знайти аналог цiєї теореми
для незалежних множин, що задовольняють умову (3) теореми 1.
Для довiльного графа Γ(V,E) позначимо
diamΓ(V,E) = sup{d(u, v) : u, v ∈ V }.
Якщо diamΓ(V,E) = ℵ0, покладемо radΓ = ℵ0. Якщо diamΓ < ℵ0 i v ∈ V , позначимо
r(v) = max{d(v, x) : x ∈ V }, radΓ = min{r(v) : v ∈ V }.
Теорема 2. Нехай Γ(V,E) — граф, r — натуральне число. Якщо rad Γ(V,E) > 2r−1− 1,
то множину V можна розбити V = V1
⋃
V2, . . . , Vr+1 так, що
indV1 = 1, indV2 6 3, . . . , indVi 6 2i − 1, . . . , indVr 6 2r − 1, indVr+1 6 2r − 1.
Теорема 3. Нехай Γ(V,E) — граф, m1,m2, . . . ,mn — натуральнi числа, такi що
|B(v,mi)| > 2i для всiх v ∈ V , i ∈ {1, 2, . . . , n}. Тодi iснує розбиття V = V1
⋃
V2, . . . , Vn,
таке, що кожна пiдмножина Vi має iндекс
indVi 6 2(mi + 2mi−1 + 22mi−2 + · · · + 2i−1m1).
Наступнi двi теореми свiдчать про те, що метод незалежних пiдмножин можна застосу-
вати для побудови розбиттiв нескiнченних графiв на нескiнченнi подмножини.
Теорема 4. Нехай Γ(V,E) — нескiнченний граф, κ — граничний кардинал. Тодi
1) множину V можна розбити на злiченне число пiдмножин скiнченного iндексу;
2) якщо для кожного кардинала κ′ < κ iснує натуральне число m, таке що |B(v,m)| >
> κ′ для всiх v ∈ V , то V можна розбити на κ пiдмножин скiнченного iндексу.
Теорема 5. Нехай Γ(V,E) — нескiнченний граф, m — натуральне число, κ — нескiн-
ченний кардинал. Тодi
1) якщо |(B(v, 1))| = κ для всiх v ∈ V , то V можна розбити на κ пiдмножин iндексу 1;
2) якщо |(B(v,m))| = κ для всiх v ∈ V , то V можна розбити на κ пiдмножин iндексу
6 3m.
1. Protasova K.D. Уравновешенные разбиения графов // Матем. заметки. – 2006. – 79. – С. 127–132.
2. Protasov I., Banakh T. Ball structures and colorings of groups and graphs // Math. Stud. Monogr. Ser. –
2003. – 11. – 147 p.
3. Protasov I.V., Protasova K.D. Automorphisms of kaleidoscopical graphs // Algebra Discrete Math. –
2007. – 2. – P. 125–129.
4. Protasov I.V., Protasova K.D. Kaleidoscopical graphs and Hamming codes // Voronoi’s Impact on Modern
Science. – 2008. – Book 4, 2. – P. 240–245.
42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №10
5. Protasova K.D. Kaleidoscopical graphs // Math. Stud. – 2002. – 18. – P. 3–9.
6. Lazebnik F., Woldar A. J. General properties of some families of graphs defined by system of equations //
J. Graph Theory. – 2001. – 38, No 2. – P. 65–68.
7. Ustimenko V.A. Coordinatization of trees and their quotiens // Voronoi’s Impact on Modern Science. –
1998. – Book 1, 2. – P. 125–152.
8. Wolder A. J. Rainbow graphs // Codes and designs. – 2002. – 10. – P. 313–322.
9. Turan P. Eine Extremalaufgabe aur der Graphentheorie // Math. Fiz. Lapok. – 1941. – 48. – P. 436–452.
10. Protasov I. V. Quasiray decomposition of infinite graphs // Math. Stud. – 2002. – 17. – P. 274–276.
Надiйшло до редакцiї 22.03.2010Київський нацiональний унiверситет
iм. Тараса Шевченка
T.M. Provotar, K. D. Protasova
Partitions of graphs by a method of independent subsets
We present a method of independent subsets for vertex partitions of graphs into subsets of controlled
indices. The index of a subset A of the set V of vertices of a graph Γ is the minimal number k
such that, for every vertex v ∈ V , there exists a path of length 6 k from v to A.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №10 43
|