WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Розкладність графів. Врівноважені розбиття скінченних графів - Реферат

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


Доведення. Нехай 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Лема 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 має 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.
Loading...

 
 

Цікаве