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

Задача 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}.

Теорема 6. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття множини вершин V=V1È V2, таке, що V1=1,. V2£ 2.

Доведення. Скористаємося схемою і позначеннями з доведення попередньої теореми. Якщо граф Grf [S] має кінцеві вершини, пофарбуємо їх зеленим кольором.

Припустимо, що Grf [S] не має циклів. Пофарбуємо корінь x цього дерева зеленим кольором. Візьмемо довільну непофарбовану вершину yÎS і обчислимо відстань d(x,y). Якщо число d(x,y) парне, пофарбуємо вершину y жовтим кольором, а інакше - зеленим. Очевидно, що S1=1, S2£2.

Припустимо, що граф Grf [S] має цикл x1, x2 ,.., xn . Можна вважати, що x2 =f(x1), x3=f(x2),…, xn=f(xn-1), x1 =f(xn). Якщо число n парне, пофарбуємо вершини циклу по черзі зеленим та жовтим кольорами. Візьмемо довільну непофарбовану вершину y. Якщо відстань від y до найближчої вершини xi циклу парна, пофарбуємо y кольором вершини xi. Якщо ця відстань непарна, пофарбуємо вершину іншим з двох кольорів. Ясно, що S1=1, S2£2.

Для непарного числа n позначимо через T1, T2, …, Tn дерева з коренями x1, x2 ,.., xn , одержані видаленням ребер циклу. Розглянемо два випадки.

Припустимо, що знайдеться вершина xi циклу, для якої дерево Ti одноелементне. Змінюючи нумерацію, можна вважати, що i=1. Пофарбуємо вершини x1, x2 зеленим кольором, а вершини x3, x4 ,.., xn пофарбуємо по черзі жовтим та зеленим кольорами. Далі продовжимо розфарбування на S як і у випадку парного числа n.

Залишилось розглянути випадок, коли всі дерева T1, T2, …, Tn не є одноелементними. Пофарбуємо вершини x1, x2 ,.., xn жовтим кольором. Візьмемо довільну непофарбовану вершину z. Якщо відстань від z до найближчої вершини циклу парна, пофарбуємо z жовтим кольором, якщо непарна, то зеленим. Як в першому, так і в другому випадках S1=1, 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ÎÁ.

Для фіксованого кардинала n множина X називається n- розкладною відносно сім'ї Á, якщо X можна розбити на n Á-щільних підмножин. В хроматичній термінології множина X є n-розкладною відносно сім'ї Á, якщо X можна розфарбувати n кольорами так, що кожна підмножина FÎÁ містить точки усіх n кольорів. Кожна n-розкладна множина X є n¢-розкладною для всіх кардиналів n¢£ n. Супремум множини кардиналів n, для яких множина X є n-розкладною відносно сім'ї Á, називається показником розкладності X відносно сім'ї Á. Зрозуміло, що множина X 1-розкладна відносно будь-якої сім'ї Á. Замість терміна “2-розкладність”, як правило, вживають термін “розкладність”. Позначимо (Á)= inf {|F|:FÎÁ}. Очевидно, показник розкладності X відносно Á не перевищує (Á). Множина X називається максимально розкладною відносно сім'ї Á, якщо X є (Á) -розкладною відносно Á.

Для довільних графа Gr(V,E) і невід'ємного цілого числа r позначимо через g (Gr,r) показник розкладності множини вершин V відносно сім'ї усіх куль {B(x,r): xÎV} радіуса r.В термінах розкладності теореми стверджують, що g(Gr,r-1) ³ r для довільних натурального числа r і зв'язного графа Gr, що має принаймні r вершин. Приклад показує, що існує скінченний зв'язний граф Gr з як завгодно великим наперед заданим локальним степенем вершин, для якого g (Gr,1)=2. Аналогічно інтерпретується і приклад 2. В задачах і теоремі 3 стверджується максимальна розкладність відповідних графів відносно сім'ї куль радіуса 1.