Реферат на тему:
Розкладність графів. Врівноважені розбиття нескінченних графів
.
графа на скінченне число підмножин має скінченний індекс, якщо всі
підмножини розбиття є підмножинами скінченного індексу. Найбільший з
індексів підмножин розбиття називається індексом розбиття.
Почнемо з поширення на нескінченні графи.
.
, що задовольняє умову
(()
.
парне.
нескінченна – теорему 1.
.
.
.
, то
,
нескінченна.
може бути як скінченним, так і нескінченним кардинальним числом.
кольорів.
кольорів.
можна застосувати стандартний діагональний процес.
кольорів? Наступний приклад дає негативну відповідь на це питання.
Більше того, він показує, що навіть 3-розфарбування з цією властивістю
може не існувати.
.
кольорів.
Для того, щоб ввести поняття врівноваженого розбиття множини вершин
нескінченного зв’язного графа дамо таке означення.
назвемо покриваючою, якщо виконуються такі умови:
;
;
зв’язний.
, якщо
є покриваючою послідовністю, а тому покриваючою буде і будь-яка її
підпослідовність.
.
Для доведення теореми скористаємося такою лемою.
;
зв’язний;
зв’язний.
теж фарбується зеленим кольором. Решта вершин дерева фарбується жовтим
кольором. Ясно, що множина зелених вершин нескінченна, проте не
виключено, що множина жовтих вершин виявилася порожньою.
, далі випишемо всі вершини першого поверху, слідом за ними всі вершини
другого поверху і т. д.
, і повторюємо для неї цю ж процедуру.
.
множини V, врівноважене відносно деякої покриваючої послідовності
скінченних підмножин множини V?
.
? Ця ж проблема відкрита навіть для дерев.
покладемо.
},
},
.
відповідно.
.
. Легко помітити, що кожна зв’язна компонента Grf [S] цього графа може
мати не більше одного циклу.
.
S2=2
Задача 3. Нехай S – напівгрупа, a(S і ax(x для всіх x(S. Довести, що
існує розбиття S=A1(A2, таке що
S=A1( a-1A1, S=A2( a-1A2( a-2A2,
де a-1Ai ={x(S : ax(Ai}, a-2Ai={x(S : a2x(Ai}.
V2( 2.
Доведення. Скористаємося схемою і позначеннями з доведення попередньої
теореми. Якщо граф Grf [S] має кінцеві вершини, пофарбуємо їх зеленим
кольором.
S2(2.
S2(2.
Для непарного числа n позначимо через T1, T2, …, Tn дерева з коренями
x1, x2 ,.., xn , одержані видаленням ребер циклу. Розглянемо два
випадки.
Припустимо, що знайдеться вершина xi циклу, для якої дерево Ti
одноелементне. Змінюючи нумерацію, можна вважати, що i=1. Пофарбуємо
вершини x1, x2 зеленим кольором, а вершини x3, x4 ,.., xn пофарбуємо по
черзі жовтим та зеленим кольорами. Далі продовжимо розфарбування на S як
і у випадку парного числа n.
S2( 2.
Задача 4. Нехай S – напівгрупа, a(S і ax(x для всіх x(S. Довести, що
існує розбиття S=A1( A2, таке що
S=A1( aA1, S=A2( a-1A2 ( a-2A2
Проаналізуємо викладені в цих двох параграфах результати з точки зору
розкладності графів.
Нехай X – довільна непорожня множина, ( – деяка сім’я її непорожніх
підмножин. Підмножина A( X називається (-щільною, якщо F( A(( для
будь-якої підмножини F((.
(() -розкладною відносно (.
Для довільних графа Gr(V,E) і невід’ємного цілого числа r позначимо
через ( (Gr,r) показник розкладності множини вершин V відносно сім’ї
усіх куль {B(x,r): x(V} радіуса r.
В термінах розкладності теореми стверджують, що ((Gr,r-1) ( r для
довільних натурального числа r і зв’язного графа Gr, що має принаймні r
вершин. Приклад показує, що існує скінченний зв’язний граф Gr з як
завгодно великим наперед заданим локальним степенем вершин, для якого (
(Gr,1)=2. Аналогічно інтерпретується і приклад 2. В задачах і теоремі 3
стверджується максимальна розкладність відповідних графів відносно сім’ї
куль радіуса 1.
Нашли опечатку? Выделите и нажмите CTRL+Enter
