UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваРозкладність графів. Врівноважені розбиття скінченних графів (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1726
Скачало298
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Розглянемо скінченний зв'язний граф 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},

-----> Page:

0 [1] [2] [3] [4]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ