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

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

Розглянемо скінченний зв’язний граф 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) називається врівноваженим, якщо існує така нумерація X1, X2, …,
Xr підмножин розбиття, для якої

|X1|=|X2|= …= |Xt| = s+1, |Xt+1| = |Xt+2| =…= |Xr| = s

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

Переформулюємо деякі з цих означень в хроматичній термінології.
Розфарбування множини X r кольорами — це довільне відображення «на» (:
X({1,2,(,r}. Кожне таке розфарбування визначає розбиття ( -1(1)( (
-1(2)( …(( -1(r) множини X на непорожні підмножини. З іншого боку, кожне
розбиття X=X1(X2(…(Xr множини X на непорожні підмножини породжується
розфарбуванням ( , що визначається за правилом: ((x)=k тоді і тільки
тоді, коли x(Xk. Розфарбування (: X({1,2,(,r} назвемо врівноваженим,
якщо відповідне розбиття X=( -1(1)((-1(2)( …(( -1(r) є врівноваженим.

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

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

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

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

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

для всіх k({0,1,…,r-1}.

Приклад 1. Розглянемо граф Grn(Vn,En), n( 2, де Vn={x1, x2, …, xn},
En={(x1, x2), (x1, x3),…, (x1, xn)}. Існує лише два 2-розфарбування (1
, (2 множини Vn, що мають індекс 1, а саме

(1(x1)=1, (1(x2)=(1(x3)=…=(1(xn)=2;

(2(x1)=2, (2(x2)=(2(x3)=…=(2(xn)=1.

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

У зв’язку з цим прикладом виникає питання про можливий аналог теореми
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 — його початком і кінцем. Таким чином, кожна
зірка є об’єднанням променів, що виходять з центра. Радіусом зірки
називається максимальна довжина її променів.

від центра розташовані вершини усіх 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 вершин від центра x вже знаходяться вершини всіх r кольорів. Для того щоб продовжити це часткове розфарбування ( на всю множину вершин V розглянемо два випадки. . Непофарбовані вершини зірки запишемо у такому порядку і пофарбуємо їх періодично зліва направо, починаючи з кольору a+b+1. Точніше, колір i-го члена v цієї послідовності визначається за формулою від x знайдуться точки усіх r кольорів. Це і означає, що індекс розфарбування ( не перевищує r. . Продовжимо розфарбування ( на множину xa, xa+1 , …, xa+b-1, yb+1, yb+2,…, yb+c, zc+1, zc+2,…, zc+a за таким правилом ((xa)=((y1), ((xa+1)=((y2),…,((xa+b-1)=((yb), ((yb+1)=((z1), ((yb+2)=((z2),…,((yb+c)=((zc), ((zc+1)=((x), ((zc+2)=((x1),…,((zc+a)=((xa-1), містять відповідно a+b+r-r1, b+c+r-r2+1, a+c+r-r3 розфарбованих різнокольорових вершин. Завершимо розфарбування за таким правилом )=((zc), )=((xa), )=((yb), Оскільки на останньому етапі розфарбування кожен колір використано не більше одного разу, то розфарбування ( врівноважене. Оскільки на відстані ( r від кожного кінця променів R1, R2, R3 розташовані вершини усіх r кольорів, то індекс розфарбування ( не перевищує r. Лема 2. Нехай r - натуральне число ( 2, Gr(V,E) - зірка з центром x радіуса ( r-1, що містить принаймні два променя довжини ( r/2. Тоді існує врівноважене r-розфарбування індексу ( r множини V. Доведення. Нехай R1, R2,…, Rt - промені довжини ( r/2, Rt+1, Rt+2,…, Rs - промені довжини < r/2, Gr(V,E) = R1(R2(…(Rt(Rt+1(…(Rs. Запропонуємо два способи розфарбування множини V в залежності від парності числа t. Якщо число t парне, занумеруємо вершини дерева R1(R2 послідовними натуральними числами у порядку їх розташування від кінця променя R1 до кінця променя R2. Продовжимо нумерацію таким же способом на вершини дерева R3(R4, пропускаючи вже занумерований центр x і т. д. Отже, початковим відрізком натурального ряду вже занумеровано вершини дерева R1(R2(…(Rt. Продовжимо цю нумерацію довільним числом на решту вершин зірки Gr(V,E) і одержимо деяке упорядкування x1,x2,…,xn множини V. Пофарбуємо вершини x1,x2,…,xn кольорами {1,2,…,r} зліва направо за правилом ((x1)=1, ((x2)=2,…, ((xr)=r, ((xr+1)=1,…,((xn)=1+(n-1)mod r. Очевидно, що розфарбування ( врівноважене. Візьмемо довільну вершину v(V. Якщо v - вершина одного з графів R1(R2, R3(R4,…, Rt-1(Rt, то у відповідному графі на відстані ( r від вершини v знаходяться вершини усіх r кольорів. Якщо ж v - вершина одного з променів Rt+1, Rt+2,…, Rs , то d(v,x)1 дерево, що має принаймні r вершин, назвемо
r-критичним, якщо після видалення будь-якого його ребра хоча б одне з
двох утворених дерев має менше ніж r вершин. Нагадаємо, що діаметром
скінченного зв’язного графу називається максимальна відстань між його
вершинами.

Лема 3. В r-критичному дереві Gr(V,E) діаметра d( r-1 знайдеться
вершина x, після видалення якої дерево розпадається на піддерева з
числом вершин r виберемо вершину x, що
задовольняє лему 1.3. Позначимо через y1,y2,…,ys усі суміжні з x вершини
дерева. Розглянемо дерева T(y1), T(y2),…,T(ys) з коренями y1,y2,…,ys,
одержані видаленням ребер (y1,x),(y2,x),…,(ys,x). В кожному з них
виберемо по одній вершині zi, що найбільше віддалена від кореня.
Позначимо через R1,R2 ,…,Rs підграфи графу Gr(V,E), що визначаються
найкоротшими шляхами від x до z1,z2,…,zs. Тоді граф S=R1(R2(…(Rs є
зіркою радіуса ( r-1.

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

Припустимо, що лише один промінь зірки S, скажімо R1, має довжину (
r/2. Серед променів R2,R3,…,Rs виберемо промінь, скажімо R2, найбільшої
довжини. Оскільки d > r, то граф R1(R2 має ( r вершин. Занумеруємо їх в
порядку розташування від кінця променя R2 до кінця променя R1 і
продовжимо цю нумерацію довільним способом на всю множину V.
Упорядковану послідовність x1,x2,…,xn вершин множини V розфарбуємо за
правилом ((xi )=1+(i-1) mod r. Врівноваженість розфарбування ( очевидна.
Візьмемо довільну вершину v(V. За означенням розфарбування ( в кулі
B(v,r) містяться r різнокольорових точок графа R1(R2. Отже, індекс
розфарбування ( не перевищує r.

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

Лема 5. Нехай Gr(V,E) — скінченний зв’язний граф, r — натуральне число
і множину вершин V розбито на підмножини V1,V2,…,Vk, так, що всі графи
Gr[V1],Gr[V2],…,Gr[Vk] зв’язні і допускають врівноважені r-розфарбування
(1,(2,…,(k , індекс яких не перевищує r. Тоді існує врівноважене
r-розфарбування ( множини V, індекс якого теж не перевищує r.

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

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

Доведення теореми 2. Для r=1 теорема очевидна. Припустимо, що r>1. Ми
можемо замінити граф його кістяком і вважати, що Gr(V,E) — дерево.
Послідовним видаленням ребер розіб’ємо множину V на підмножини
V1,V2,…,Vk так, що Gr[V1],Gr[V2],…,Gr[Vk] — r-критичні дерева.
Застосуємо леми 1.4 і 1.5.

Приклад 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}. Застосуємо теорему 2 до кожної
зв’язної компоненти графа Cay(G), а потім — лему 5. Отримаємо таке
твердження.

Існує врівноважене розбиття групи G=A1(A2(…(Ar, таке що G=SrAi для всіх
i({1,2,…,r}.

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

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

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

Приклад 3. Для кожного натурального числа m покладемо Xm={1,2,…,3m} і
позначимо через Ym сім’ю усіх m-підмножин множини Xm. Розглянемо граф
Grm з множиною вершин Vm = Xm( Ym і множиною ребер Em, де (x,y)(Em тоді
і тільки тоді, коли x(Xm , y(Ym і x(y. Зауважимо, що локальний ступінь
кожної вершини графа Grm не менший за m. Зафіксуємо довільне
3-розфарбування (: Vm ? {1,2,3} . Оскільки |Xm=3m|, то знайдеться
однокольорова m-підмножина у множини Xm. Значить, |((B(y,1))|<3.

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