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

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.