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

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

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

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


Реферат на тему:
Розкладність графів. Врівноважені розбиття скінченних графів
Розглянемо скінченний зв'язний граф 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}, таке що
для всіх x V1, k {0,1,…,r-1}. Зауважимо, що і виберемо максимальне число m {0,1,…,r-2} для якого . Далі виберемо довільне число s {0,1,…,r}, таке що . Покладемо (y)=s і (x)= 1(x) для всіх x V1. Оскільки B(z,k) B(y,k+1), то для всіх 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 - його початком і кінцем. Таким чином, кожна зірка є об'єднанням променів, що виходять з центра. Радіусом зірки називається максимальна довжина її променів.
Лема 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 цієї послідовності визначається за формулою
Врівноваженість розфарбування очевидна. Візьмемо довільну вершину v V. Якщо v - вершина графа R1 R2, то за означенням на відстані r-1 від v розташовані вершини графа R1 R2 усіх 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
за таким правилом
(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),
Таким чином, розфарбовано 2r вершин зірки, причому кожен з r кольорів використано двічі. Зауважимо також, що кулі містять відповідно
a+b+r-r1, b+c+r-r2+1, a+c+r-r3
розфарбованих різнокольорових вершин. Завершимо розфарбування за таким правилом
(xa+b)= ( ), (xa+b+1)= ( ),…, ( )= (zc),
(yb+c+1)= ( ), (yb+c+2)= ( ),…, ( )= (xa),
(zc+a+1)= ( ), (zc+a+2)= ( ),…, ( )= (yb),
Оскільки на останньому етапі розфарбування кожен колір використано не більше одного разу, то розфарбування врівноважене. Оскільки на відстані r від кожного кінця променів R1, R2, R3 розташовані вершини усіх r кольорів, то індекс розфарбування не перевищує r.
Лема 2. Нехай r - натуральне число 2, Gr(V,E) - зірка з центром x радіуса r-1, що містить принаймні два променя довжини r/2. Тоді існує врівноважене r-розфарбування індексу r множини V.
Loading...

 
 

Цікаве