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

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

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

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