Реферат на тему:

Розкладність графів. Врівноважені розбиття нескінченних графів

.

графа на скінченне число підмножин має скінченний індекс, якщо всі
підмножини розбиття є підмножинами скінченного індексу. Найбільший з
індексів підмножин розбиття називається індексом розбиття.

Почнемо з поширення на нескінченні графи.

.

, що задовольняє умову

(()

.

парне.

нескінченна — теорему 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.

Похожие записи