§1. Врівноважені розбиття скінченних графів

Розглянемо скінченний зв'язний граф Gr = (V,E) з множиною вершин V і множиною ребер E. Для довільних двох вершин x,yÎV позначимо через d(x,y) довжину найкоротшого шляху від x до y. Для довільних вершини xÎV, підмножини AÍV і невід'ємного цілого числа m покладемо

Індексом непорожньої підмножини AÍV називається найменше невід'ємне ціле число m, таке що V=B(A,m). Індекс підмножини A позначимо через ind A.

Відстань dist(A,B) між непорожніми підмножинами А, В множини вершин V визначимо за формулою

Зауважимо, що ind A=dist(A,V) для будь-якої непорожньої підмножини AÍV.

Індексом розбиття множини вершин V на непорожні підмножини називається максимальний індекс підмножин розбиття.

Розбиття скінченної множини X, |X|=n на r підмножин (1£ r £ n, n=rs+t, 0 £ t < r) називається врівноваженим, якщо існує така нумерація X₁, X₂, …, X_r підмножин розбиття, для якої

|X₁|=|X₂|= …= |X_t| = s+1, |X_t+1| = |X_t+2| =…= |X_r| = s

Зокрема, якщо r - дільник числа n, то врівноважене розбиття X - це розбиття X на r частин, що мають однакову кількість елементів.

Переформулюємо деякі з цих означень в хроматичній термінології. Розфарбування множини X r кольорами - це довільне відображення "на" c: X®{1,2,¼,r}. Кожне таке розфарбування визначає розбиття c ^-1(1)È c ^-1(2)È …Èc ^-1(r) множини X на непорожні підмножини. З іншого боку, кожне розбиття X=X₁ÈX₂È…ÈX_r множини X на непорожні підмножини породжується розфарбуванням c , що визначається за правилом: c(x)=k тоді і тільки тоді, коли xÎX_k. Розфарбування c: X®{1,2,¼,r} назвемо врівноваженим, якщо відповідне розбиття X=c ^-1(1)Èc^-1(2)È …Èc ^-1(r) є врівноваженим.

Розбиття множини V вершин графа Gr = (V,E) на r підмножин має індекс £ m тоді і тільки тоді, коли при разфарбуванні c: V®{1,2,¼,r}, що відповідає цьому розбиттю, кожна куля B(x,m), xÎV містить точки усіх r кольорів. Індексом розфарбування називається індекс відповідного розбиття.

Теорема 1.1. Для будь-яких натуральних чисел r, n, r £ n і довільного зв'язного графа Gr = (V,E), |V|=n існує розбиття індексу £ r-1 множини вершин V на r підмножин.

Доведення. Індукцією по числу n покажемо, що існує розфарбування c: V®{1,2,¼,r}, таке що

для будь-яких xÎV, kÎ{0,1,…,r-1}. Теорема випливає з цього твердження при k=r-1.

Ми можемо замінити граф його кістяком і вважати, що Gr = (V,E) є деревом. Для n=1 твердження очевидне. Якщо r=n, то можна вибрати довільне розфарбування c: V®{1,2,¼,r}. Припустимо, що r<n, n>1 і зафіксуємо будь-яку кінцеву вершину y дерева Gr = (V,E). Тоді B(y,1)={y,z}, де z - єдина суміжна з y вершина дерева Gr = (V,E). Розглянемо граф Gr₁(V₁,E₁), де V₁=V \ {y}, E₁=E \ {(y,z)}. Позначимо через B₁(x,k) кулю радіуса k в графі Gr₁(V₁,E₁) з центром в точці xÎV₁. Оскільки граф Gr₁(V₁,E₁) зв'язний і |V₁|=n-1, то за припущенням індукції існує розфарбування c₁: V₁®{1,2,¼,r}, таке що

для всіх xÎV₁, kÎ{0,1,…,r-1}. Зауважимо, що і виберемо максимальне число mÎ{0,1,…,r-2} для якого . Далі виберемо довільне число sÎ{0,1,…,r}, таке що . Покладемо c(y)=s і c(x)=c₁(x) для всіх xÎV₁. Оскільки B(z,k)ÍB(y,k+1), то для всіх kÎ{0,1,…,r-1}.

Приклад 1.1. Розглянемо граф Gr_n(V_n,E_n), n³ 2, де V_n={x₁, x₂, …, x_n}, E_n={(x₁, x₂), (x₁, x₃),…, (x₁, x_n)}. Існує лише два 2-розфарбування c₁ , c₂ множини V_n, що мають індекс 1, а саме

c₁(x₁)=1, c₁(x₂)=c₁(x₃)=…=c₁(x_n)=2;

c₂(x₁)=2, c₂(x₂)=c₂(x₃)=…=c₂(x_n)=1.

Якщо n>3, то ці розфарбування неврівноважені. Отже, для n>3 і r=2 не існує врівноважених розфарбувань індексу r-1 множини c_n.

У зв'язку з цим прикладом виникає питання про можливий аналог теореми 1.1 для врівноважених розбиттів.

Теорема 1.2. Для будь-яких натуральних чисел r, n, r£ n і довільного зв'язного графа Gr(V,E), |V|=n існує врівноважене розбиття індексу £ r множини вершин V на r підмножин.

Для доведення цієї теореми необхідні деякі означення і технічні результати.

Скінченне дерево Gr(V,E), |V|>2 називається зіркою з центром xÎV, якщо x не є кінцевою вершиною дерева і будь-які два найкоротших шляхи від x до різних кінцевих вершин не мають спільних ребер. Кожен такий шлях x=x₀, x₁,…,x_k визначає промінь зірки з множиною вершин {x₀, x₁,…,x_k} і множиною ребер {(x₀, x₁), (x₁, x₂),…, (x_k-1, x_k)}. Число k називається довжиною променя, а x₀ і x₁ - його початком і кінцем. Таким чином, кожна зірка є об'єднанням променів, що виходять з центра. Радіусом зірки називається максимальна довжина її променів.

Лема 1.1. Нехай - r натуральне число, r>2, Gr(V,E) - зірка з центром x і трьома променями R₁, R₂, R₃ радіусів r₁, r₂, r₃, причому iÎ{1, 2, 3}. Тоді існує врівноважене r-розфарбування індексу £ r множини вершин V, таке що на відстані від центра розташовані вершини усіх r кольорів.

Доведення. Припустимо для визначеності, що r₁³ r₂³ r₃. Запишемо вершини променів R₁, R₂, R₃ у порядку їх розташування від початку променя до його кінця

.

Якщо r=2, то r₁=r₂=r₃=1 і будь-яке врівноважене 2-розфарбування має індекс 2.

Припустимо, що r>2, r=3r'+j, 0£ j<3. Подамо число r у вигляді суми r = a+b+c, a³ b³ c=r'.

Розглянемо послідовність r вершин

і пофарбуємо їх кольорами {1,2,..r} зліва направо. Оскільки r'+1 £ r/3 + 1, то на відстані від центра x вже знаходяться вершини всіх r кольорів. Для того щоб продовжити це часткове розфарбування c на всю множину вершин V розглянемо два випадки.

Випадок . Не пофарбовані вершини зірки запишемо у такому порядку

і пофарбуємо їх періодично зліва направо, починаючи з кольору a+b+1. Точніше, колір i-го члена v цієї послідовності визначається за формулою

Врівноваженість розфарбування c очевидна. Візьмемо довільну вершину vÎV. Якщо v - вершина графа R₁ÈR₂, то за означенням c на відстані £ r-1 від v розташовані вершини графа R₁ÈR₂ усіх r кольорів. Якщо ж v - вершина променя R₃, то d(v,x)<2/3´ r, а на відстані від x знайдуться точки усіх r кольорів. Це і означає, що індекс розфарбування c не перевищує r.

Випадок . Продовжимо розфарбування c на множину

x_a, x_a+1 , …, x_a+b-1, y_b+1, y_b+2,…, y_b+c, z_c+1, z_c+2,…, z_c+a

за таким правилом

c(x_a)=c(y₁), c(x_a+1)=c(y₂),…,c(x_a+b-1)=c(y_b),

c(y_b+1)=c(z₁), c(y_b+2)=c(z₂),…,c(y_b+c)=c(z_c),

c(z_c+1)=c(x), c(z_c+2)=c(x₁),…,c(z_c+a)=c(x_a-1),

Таким чином, розфарбовано 2r вершин зірки, причому кожен з r кольорів використано двічі. Зауважимо також, що кулі містять відповідно

a+b+r-r₁, b+c+r-r₂+1, a+c+r-r₃

розфарбованих різнокольорових вершин. Завершимо розфарбування за таким правилом

c(x_a+b)=c(), c(x_a+b+1)=c(),…,c()=c(z_c),

c(y_b+c+1)=c(), c(y_b+c+2)=c(),…,c()=c(x_a),

c(z_c+a+1)=c(), c(z_c+a+2)=c(),…,c()=c(y_b),

Оскільки на останньому етапі розфарбування кожен колір використано не більше одного разу, то розфарбування c врівноважене. Оскільки на відстані £ r від кожного кінця променів R₁, R₂, R₃ розташовані вершини усіх r кольорів, то індекс розфарбування c не перевищує r.

Лема 1.2. Нехай r - натуральне число ³ 2, Gr(V,E) - зірка з центром x радіуса £ r-1, що містить принаймні два променя довжини ³ r/2. Тоді існує врівноважене r-розфарбування індексу £ r множини V.

Доведення. Нехай R₁, R₂,…, R_t - промені довжини ³ r/2, R_t+1, R_t+2,…, R_s - промені довжини < r/2,

Gr(V,E) = R₁ÈR₂È…ÈR_tÈR_t+1È…ÈR_s.

Запропонуємо два способи розфарбування множини V в залежності від парності числа t.

Якщо число t парне, занумеруємо вершини дерева R₁ÈR₂ послідовними натуральними числами у порядку їх розташування від кінця променя R₁ до кінця променя R₂. Продовжимо нумерацію таким же способом на вершини дерева R₃ÈR₄, пропускаючи вже занумерований центр x і т. д. Отже, початковим відрізком натурального ряду вже занумеровано вершини дерева R₁ÈR₂È…ÈR_t. Продовжимо цю нумерацію довільним числом на решту вершин зірки Gr(V,E) і одержимо деяке упорядкування x₁,x₂,…,x_n множини V. Пофарбуємо вершини x₁,x₂,…,x_n кольорами {1,2,…,r} зліва направо за правилом

c(x₁)=1, c(x₂)=2,…, c(x_r)=r, c(x_r+1)=1,…,c(x_n)=1+(n-1)mod r.

Очевидно, що розфарбування c врівноважене. Візьмемо довільну вершину vÎV. Якщо v - вершина одного з графів R₁ÈR₂, R₃ÈR₄,…, R_t-1ÈR_t, то у відповідному графі на відстані £ r від вершини v знаходяться вершини усіх r кольорів. Якщо ж v - вершина одного з променів R_t+1, R_t+2,…, R_s , то d(v,x)<r/2, а в графі R₁ÈR₂ на відстані £ r/2 від центра x також містяться вершини усіх r кольорів. Це і означає, що індекс розфарбування c не перевищує r.

Якщо число t непарне, пофарбуємо вершини зірки R₁ÈR₂ÈR₃ згідно з лемою 1.1. Позначимо через m число вершин зірки R₁ÈR₂ÈR₃, m=ra+b, 0£b<r. Змінюючи нумерацію кольорів, можна вважати, що кольори {1,2,…,b} використано a+1 разів, а кольори {b+1, b+2,…,r} використано a разів. Починаючи з кольору (b+1) mod r, продовжимо це розфарбування на V таким же чином, як і у випадку парного числа t. Візьмемо довільну вершину vÎV. Якщо v - вершина одного з графів R₁ÈR₂ÈR₃, R₄ÈR₅,…, R_t-1ÈR_t, то у відповідному графі на відстані £ r від вершини v містяться вершини усіх r кольорів. Якщо ж v - вершина одного з променів R_t+1, R_t+2,…, R_s , то d(v,x)<r/2, а на відстані £ r/3 +1 від x в графі R₁ÈR₂ÈR₃ також містяться вершини усіх r кольорів. Отже, індекс розфарбування не перевищує r.

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

Лема 1.3. В r-критичному дереві Gr(V,E) діаметра d³ r-1 знайдеться вершина x, після видалення якої дерево розпадається на піддерева з числом вершин <r в кожному з них.

Доведення. Виберемо вершини v₀,v_dÎ V, такі що d(v₀,v_d )=d. Нехай v₀,v₁, …,v_d - найкоротший шлях від вершини v₀ до вершини v_d. Для кожного числа iÎ{1,2,…,d} позначимо через T_i дерево з коренем v_i, утворене видаленням з Gr(V,E) ребра (v_i-1,v_i). Виберемо мінімальне число mÎ{1,2,…,d}, таке що дерево T_m має <r вершин. Покладемо x=v_m-1. Для кожної вершини y, суміжної з вершиною x, позначимо через T(y) дерево з коренем y, утворене видаленням ребра (x,y). Якщо yÏ{v₀,v₁, …,v_d}, то число вершин дерева T(y) менше ніж r в силу r-критичності графа Gr(V,E). Це ж твердження справедливе і для кожної вершини yÎ{v₀,v₁, …,v_d} в силу вибору числа m і r-критичності.

Лема 1.4. Для кожного r-критичного дерева Gr(V,E) існує врівноважене r-розфарбування множини вершин V, індекс якого не перевищує r.

Доведення. Якщо діаметр d дерева £ r, то будь-яке r-розфарбування множини вершин V має індекс £ r. Для d >r виберемо вершину x, що задовольняє лему 1.3. Позначимо через y₁,y₂,…,y_s усі суміжні з x вершини дерева. Розглянемо дерева T(y₁), T(y₂),…,T(y_s) з коренями y₁,y₂,…,y_s, одержані видаленням ребер (y₁,x),(y₂,x),…,(y_s,x). В кожному з них виберемо по одній вершині z_i, що найбільше віддалена від кореня. Позначимо через R₁,R₂ ,…,R_s підграфи графу Gr(V,E), що визначаються найкоротшими шляхами від x до z₁,z₂,…,z_s. Тоді граф S=R₁ÈR₂È…ÈR_s є зіркою радіуса £ r-1.

Припустимо, що серед променів зірки S є принаймні два довжини ³ r/2. За лемою 1.2 існує врівноважене r-розфарбування індексу £ r множини вершин зірки S. Продовжимо його довільним чином до врівноваженого розфарбування c множини S. Візьмемо довільну вершину vÎV, v¹x і виберемо піддерево T(y_i), вершиною якого є v. Оскільки число вершин дерева T(y_i) менше r, то B(z_i,r)ÍB(v,r). Оскільки куля B(z_i,r) містить точки усіх r кольорів зірки S, то розфарбування c має індекс£ r.

Припустимо, що лише один промінь зірки S, скажімо R₁, має довжину ³ r/2. Серед променів R₂,R₃,…,R_s виберемо промінь, скажімо R₂, найбільшої довжини. Оскільки d > r, то граф R₁ÈR₂ має ³ r вершин. Занумеруємо їх в порядку розташування від кінця променя R₂ до кінця променя R₁ і продовжимо цю нумерацію довільним способом на всю множину V. Упорядковану послідовність x₁,x₂,…,x_n вершин множини V розфарбуємо за правилом c(x_i )=1+(i-1) mod r. Врівноваженість розфарбування c очевидна. Візьмемо довільну вершину vÎV. За означенням розфарбування c в кулі B(v,r) містяться r різнокольорових точок графа R₁ÈR₂. Отже, індекс розфарбування c не перевищує r.

Для підмножини A множини вершин графа Gr(V,E) позначимо через Gr[A] граф з множиною вершин A і множиною ребер EÇ(A´A).

Лема 1.5. Нехай Gr(V,E) - скінченний зв'язний граф, r - натуральне число і множину вершин V розбито на підмножини V₁,V₂,…_,V_k, так, що всі графи Gr[V₁],Gr[V₂],…,Gr[V_k] зв'язні і допускають врівноважені r-розфарбування c₁,c₂,…,c_k , індекс яких не перевищує r. Тоді існує врівноважене r-розфарбування c множини V, індекс якого теж не перевищує r.

Доведення. Нехай . Змінюючи нумерацію кольорів, можна вважати, що c_i(x_ij)=1+(j-1)modr для всіх iÎ{1,2,…,k}, jÎ{1,2,…,m_i}. Запишемо вершини множини V у послідовність

і для i-го члена v цієї послідовності покладемо c(v)=1+(i-1)mod r .

Доведення теореми 1.2. Для r=1 теорема очевидна. Припустимо, що r>1. Ми можемо замінити граф його кістяком і вважати, що Gr(V,E) - дерево. Послідовним видаленням ребер розіб'ємо множину V на підмножини V₁,V₂,…_,V_k так, що Gr[V₁],Gr[V₂],…,Gr[V_k] - r-критичні дерева. Застосуємо леми 1.4 і 1.5.

Приклад 1.2. Нехай G - скінченна група з одиницею e, SÍG, |S|=r, S=S^-1, eÎS. Розглянемо граф Келі Cay(G) групи G з множиною вершин G і множиною ребер {(x,y): x,yÎG, x¹y, xy^-1ÎS}. Застосуємо теорему 1.2 до кожної зв'язної компоненти графа Cay(G), а потім - лему 1.5. Отримаємо таке твердження.

Існує врівноважене розбиття групи G=A₁ÈA₂È…ÈA_r, таке що G=S^rA_i для всіх iÎ{1,2,…,r}.

Якщо S - підгрупа групи G, то вказати таке розбиття дуже просто: кожен лівий суміжний клас групи G за підгрупою S пофарбуємо кольорами {1,2,…,r} і позначимо через A₁,A₂,…,A_r однокольорові підмножини. Отже, теорему 1.2 можна розглядати як аналог для графів теореми Лагранжа про розклад групи на суміжні класи за підгрупою.

У зв'язку з теоремою 1.1 виникає таке питання. Чи можна множину вершин скінченного зв'язного графа розбити на підмножин індексу 1 за умови, що локальний ступінь кожної вершини досить великий? Нагадаємо, що локальний ступінь вершини - це кількість ребер, що виходять з цієї вершини. Уточнимо це питання. Чи для кожного натурального числа r знайдеться натуральне число f(r), таке що будь-який скінченний зв'язний граф з локальними ступенями вершин ³ f(r) можна розфарбувати r кольорами так, що кожна куля радіуса 1 містить вершини усіх r кольорів?

Числа f(1), f(2) визначаються теоремою 1.1: f(1)=f(2)=1. Наступний приклад показує, що числа f(3) взагалі не існує.

Приклад 1.3. Для кожного натурального числа m покладемо X_m={1,2,…,3m} і позначимо через Y_m сім'ю усіх m-підмножин множини X_m. Розглянемо граф Gr_m з множиною вершин V_m = X_mÈ Y_m і множиною ребер E_m, де (x,y)ÎE_m тоді і тільки тоді, коли xÎX_m , yÎY_m і xÎy. Зауважимо, що локальний ступінь кожної вершини графа Gr_m не менший за m. Зафіксуємо довільне 3-розфарбування c: V_m → {1,2,3} . Оскільки |X_m=3m|, то знайдеться однокольорова m-підмножина у множини X_m. Значить, |c(B(y,1))|<3.