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

У зв'язку з цим прикладом виникає питання про можливий аналог теореми 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=x0, x1,…,xk визначає промінь зірки з множиною вершин {x0, x1,…,xk} і множиною ребер {(x0, x1), (x1, x2),…, (xk-1, xk)}. Число k називається довжиною променя, а x0 і x1 - його початком і кінцем. Таким чином, кожна зірка є об'єднанням променів, що виходять з центра. Радіусом зірки називається максимальна довжина її променів.

Лема 1. Нехай - r натуральне число, r>2, Gr(V,E) - зірка з центром x і трьома променями R1, R2, R3 радіусів r1, r2, r3, причому i{1, 2, 3}. Тоді існує врівноважене r-розфарбування індексу r множини вершин V, таке що на відстані від центра розташовані вершини усіх r кольорів.

Доведення. Припустимо для визначеності, що r1 r2 r3. Запишемо вершини променів R1, R2, R3 у порядку їх розташування від початку променя до його кінця

Якщо r=2, то r1=r2=r3=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 , то на відстані від центра x вже знаходяться вершини всіх r кольорів. Для того щоб продовжити це часткове розфарбування на всю множину вершин V розглянемо два випадки.

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

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

Врівноваженість розфарбування очевидна. Візьмемо довільну вершину vV. Якщо v - вершина графа R1R2, то за означенням на відстані r-1 від v розташовані вершини графа R1R2 усіх r кольорів. Якщо ж v - вершина променя R3, то d(v,x) , а на відстані від x знайдуться точки усіх r кольорів. Це і означає, що індекс розфарбування не перевищує r.

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

xa, xa+1 , …, xa+b-1, yb+1, yb+2,…, yb+c, zc+1, zc+2,…, zc+a

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

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

a+b+r-r1, b+c+r-r2+1, a+c+r-r3

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

Оскільки на останньому етапі розфарбування кожен колір використано не більше одного разу, то розфарбування врівноважене. Оскільки на відстані r від кожного кінця променів R1, R2, R3 розташовані вершини усіх r кольорів, то індекс розфарбування  не перевищує r.

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