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

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

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

Розглянемо скінченний зв «язний граф 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® множини X на непорожні підмножини. З іншого боку, кожне розбиття X=X1(X2(…(Xr множини X на непорожні підмножини породжується розфарбуванням (, що визначається за правилом: ((x)=k тоді і тільки тоді, коли x (Xk. Розфарбування (: X ({1,2,(, r} назвемо врівноваженим, якщо відповідне розбиття X=(-1(1)((-1(2)(…((-1® є врівноваженим.

Розбиття множини 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).

Якщо число t непарне, пофарбуємо вершини зірки R1(R2(R3 згідно з лемою 1.1. Позначимо через m число вершин зірки R1(R2(R3, m=ra+b, 0(b.

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

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

Доведення. Виберемо вершини v0, vd (V, такі що d (v0,vd)=d. Нехай v0, v1, …, vd — найкоротший шлях від вершини v0 до вершини vd. Для кожного числа i ({1,2,…, d} позначимо через Ti дерево з коренем vi, утворене видаленням з Gr (V, E) ребра (vi-1,vi). Виберемо мінімальне число m ({1,2,…, d}, таке що дерево Tm має.

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

Доведення. Якщо діаметр d дерева (r, то будь-яке r-розфарбування множини вершин V має індекс (r. Для d >r виберемо вершину x, що задовольняє лему 1.3. Позначимо через y1, y2,…, ys усі суміжні з x вершини дерева. Розглянемо дерева T (y1), T (y2),…, T (ys) з коренями y1, y2,…, ys, одержані видаленням ребер (y1,x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (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®, таке що будь-який скінченний зв «язний граф з локальними ступенями вершин (f® можна розфарбувати 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 x2192 {1,2,3}. Оскільки |Xm=3m|, то знайдеться однокольорова m-підмножина у множини Xm. Значить, |((B (y, 1))|<3.