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

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

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

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

множини беремо першу за списком зелену вершину, що не увійшла до , і повторюємо для неї цю ж процедуру.
Доведення теореми 4. Скористаємось розбиттям з леми 1 і покладемо . Очевидно, що - покриваюча послідовність. До кожного з графів , застосуємо теорему і зафіксуємо врівноважене -розфарбування індексу . За лемою ці розфарбування можна вибрати так, що є продовженням розфарбування c, . За візьмемо відображення , звуження якого на кожну з підмножин співпадає з . Ясно що розфарбування породжує -розбиття індексу , врівноважене відносно послідовності .
Проблема 1. Нехай Gr(V,E) - довільний зліченний зв'язний граф, - натуральне число. Чи існує - розфарбування індексу множини V, врівноважене відносно деякої покриваючої послідовності скінченних підмножин множини V?
З доведення теореми 4 випливає, що для позитивної відповіді на це питання досить поширити лему 1 на довільні зліченні зв'язні графи. Проте цей шлях безперспективний. Дійсно, розглянемо дерево Gr(V,E) з множиною вершин і множиною ребер . Очевидно, що множина вершин цього дерева не допускає розбиттів, що задовольняють умови леми 1 при .
Проблема 2. Нехай Gr(V,E) - зліченний локально скінченний зв'язний граф, , - довільне натуральне число. Чи існує розбиття індексу множини V на підмножин, врівноважене відносно послідовності ? Ця ж проблема відкрита навіть для дерев.
Розглянемо орієнтовний граф Gr(V,E) з множиною вершин V і множиною орієнтовних ребер E. Вважаємо, що граф не має петель і кратних ребер. Для довільних вершин , підмножини і невід'ємного цілого числа покладемо.
існує орієнтовний шлях довжини від до },
існує орієнтовний шлях довжини від до },
В цих позначеннях враховується, що , для всіх , .
За означенням підмножина має скінченний індекс , (відповідно ), якщо знайдеться таке невід'ємне ціле число , що (відповідно ). Найменші невід'ємні цілі числа, для яких виконуються ці рівності, позначимо через A та відповідно.
Теорема 5. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття , таке що , .
Доведення. Для кожної вершини виберемо вершину , для якої існує ребро . Таким чином ми визначили відображення . Розглянемо неорієнтовний граф Grf(V,Ef) цього відображення з множиною неорієнтовних ребер . Легко помітити, що кожна зв'язна компонента Grf [S] цього графа може мати не більше одного циклу.
Припустимо, що Grf [S] не має жодного циклу. В цьому випадку Grf [S] - нескінченне дерево. Виберемо довільну вершину і назвемо її коренем. Пофарбуємо корінь зеленим кольором. Візьмемо довільну вершину . Якщо відстань від до непарна, пофарбуємо жовтим кольором, а якщо парна - зеленим. Позначимо через і підмножини всіх зелених та жовтих вершин відповідно. Ясно, що .
Нехай в графі Grf [S] є цикл . Якщо число n парне, пофарбуємо вершини циклу по черзі зеленим та жовтим кольорами. Для непарного числа n пофарбуємо вершини x1, x2 зеленим кольором, а вершини x3, x4 ,.., xn по черзі - жовтим та зеленим кольорами. Візьмемо довільну вершину y, що не належить циклу. Виберемо вершину циклу xi, найближчу за відстанню до вершини y. Якщо ця відстань парна, пофарбуємо y кольором вершини xi, якщо непарна, то в інший з двох кольорів. Позначимо через S1 та S2 множини зелених та жовтих вершин. Якщо число n парне, то S1= S2=1. Якщо число n непарне, то S1=1, S2=2
Задача 3. Нехай S - напівгрупа, a S і ax x для всіх x S. Довести, що існує розбиття S=A1 A2, таке що
S=A1 a-1A1, S=A2 a-1A2 a-2A2,
де a-1Ai ={x S : ax Ai}, a-2Ai={x S : a2x Ai}.
Теорема 6. Нехай Gr(V,E) - орієнтовний граф, з кожної вершини якого виходить принаймні одне орієнтовне ребро. Тоді існує розбиття множини вершин V=V1 V2, таке, що V1=1,. V2 2.
Доведення. Скористаємося схемою і позначеннями з доведення попередньої теореми. Якщо граф Grf [S] має кінцеві вершини, пофарбуємо їх зеленим кольором.
Припустимо, що Grf [S] не має циклів. Пофарбуємо корінь x цього дерева зеленим кольором. Візьмемо довільну непофарбовану вершину y S і обчислимо відстань d(x,y). Якщо число d(x,y) парне, пофарбуємо вершину y жовтим кольором, а інакше - зеленим. Очевидно, що S1=1, S2 2.
Припустимо, що граф Grf [S] має цикл x1, x2 ,.., xn . Можна вважати, що x2 =f(x1), x3=f(x2),…, xn=f(xn-1), x1 =f(xn). Якщо число n парне, пофарбуємо вершини циклу по черзі зеленим та жовтим кольорами. Візьмемо довільну непофарбовану вершину y. Якщо відстань від y до найближчої вершини xi циклу парна, пофарбуємо y кольором вершини xi. Якщо ця відстань непарна, пофарбуємо вершину іншим з двох кольорів. Ясно, що S1=1, S2 2.
Для непарного числа n позначимо через T1, T2, …, Tn дерева з коренями x1, x2 ,.., xn , одержані видаленням ребер циклу. Розглянемо два випадки.
Припустимо, що знайдеться вершина xi циклу, для якої дерево Ti одноелементне. Змінюючи нумерацію, можна вважати, що i=1. Пофарбуємо вершини x1, x2 зеленим кольором, а вершини x3, x4 ,.., xn пофарбуємо по черзі жовтим та зеленим кольорами. Далі продовжимо розфарбування на S як і у випадку парного числа n.
Залишилось розглянути випадок, коли всі дерева T1, T2, …, Tn не є одноелементними. Пофарбуємо вершини x1, x2 ,.., xn жовтим кольором. Візьмемо довільну непофарбовану вершину z. Якщо відстань від z до найближчої вершини циклу парна, пофарбуємо z жовтим кольором, якщо непарна, то зеленим. Як в першому, так і в другому випадках S1=1, S2 2.
Задача 4. Нехай S - напівгрупа, a S і ax x для всіх x S. Довести, що існує розбиття S=A1 A2, таке що
S=A1 aA1, S=A2 a-1A2 a-2A2
Проаналізуємо викладені в цих двох параграфах результати з точки зору розкладності графів.
Нехай X - довільна непорожня множина, - деяка сім'я її непорожніх підмножин. Підмножина A X називається -щільною, якщо F A для будь-якої підмножини F .
Для фіксованого кардинала n множина X називається n- розкладною відносно сім'ї , якщо X можна розбити на n -щільних підмножин. В хроматичній термінології множина X є n-розкладною відносно сім'ї , якщо X можна розфарбувати n кольорами так, що кожна підмножина F містить точки усіх n кольорів. Кожна n-розкладна множина X є n -розкладною для всіх кардиналів n n. Супремум множини кардиналів n, для яких множина X є n-розкладною відносно сім'ї , називається показником розкладності X відносно сім'ї . Зрозуміло, що множина X 1-розкладна відносно будь-якої сім'ї .Замість терміна "2-розкладність", як правило, вживають термін "розкладність". Позначимо ( )= inf {|F|:F }. Очевидно, показник розкладності X відносно не перевищує ( ). Множина X називається максимально розкладною відносно сім'ї , якщо X є ( ) -розкладною відносно .
Для довільних графа Gr(V,E) і невід'ємного цілого числа r позначимо через (Gr,r) показник розкладності множини вершин V відносно сім'ї усіх куль {B(x,r): x V} радіуса r.
В термінах розкладності теореми стверджують, що (Gr,r-1) r для довільних натурального числа r і зв'язного графа Gr, що має принаймні r вершин. Приклад показує, що існує скінченний зв'язний граф Gr з як завгодно великим наперед заданим локальним степенем вершин, для якого (Gr,1)=2. Аналогічно інтерпретується і приклад 2. В задачах і теоремі 3 стверджується максимальна розкладність відповідних графів відносно сім'ї куль радіуса 1.
Loading...

 
 

Цікаве