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

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 17

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

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

 

ПОШУК:   

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

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

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

 

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

 

.

 

графа на скінченне число підмножин має скінченний індекс, якщо всі

підмножини розбиття є підмножинами скінченного індексу. Найбільший з

індексів підмножин розбиття називається індексом розбиття.

 

Почнемо з поширення на нескінченні графи.

 

.

 

, що задовольняє умову

 

(()

 

.

 

парне.

 

нескінченна - теорему 1.

 

.

 

.

 

.

 

, то

 

,

 

нескінченна.

 

може бути як скінченним, так і нескінченним кардинальним числом.

 

кольорів.

 

кольорів.

 

можна застосувати стандартний діагональний процес.

 

кольорів? Наступний приклад дає негативну відповідь на це питання.

Більше того, він показує, що навіть 3-розфарбування з цією властивістю

може не існувати.

 

.

 

кольорів.

 

Для того, щоб ввести поняття врівноваженого розбиття множини вершин

нескінченного зв'язного графа дамо таке означення.

 

назвемо покриваючою, якщо виконуються такі умови:

 

;

 

;

 

зв'язний.

 

, якщо

 

 

є покриваючою послідовністю, а тому покриваючою буде і будь-яка її

підпослідовність.

 

.

 

Для доведення теореми скористаємося такою лемою.

 

 

;

 

зв'язний;

 

зв'язний.

 

теж фарбується зеленим кольором. Решта вершин дерева фарбується жовтим

кольором. Ясно, що множина зелених вершин нескінченна, проте не

виключено, що множина жовтих вершин виявилася порожньою.

 

, далі випишемо всі вершини першого поверху, слідом за ними всі вершини

другого поверху і т. д.

 

, і повторюємо для неї цю ж процедуру.

 

.

 

множини V, врівноважене відносно деякої покриваючої послідовності

скінченних підмножин множини V?

 

.

 

? Ця ж проблема відкрита навіть для дерев.

 

покладемо.

 

},

 

},

 

 

.

 

відповідно.

 

.

 

. Легко помітити, що кожна зв'язна компонента Grf [S] цього графа може

мати не більше одного циклу.

 

.

 

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}.

 

V2( 2.

 

Доведення. Скористаємося схемою і позначеннями з доведення попередньої

теореми. Якщо граф Grf [S] має кінцеві вершини, пофарбуємо їх зеленим

кольором.

 

S2(2.

 

S2(2.

 

Для непарного числа n позначимо через T1, T2, …, Tn дерева з коренями

x1, x2 ,.., xn , одержані видаленням ребер циклу. Розглянемо два

випадки.

 

Припустимо, що знайдеться вершина xi циклу, для якої дерево Ti

одноелементне. Змінюючи нумерацію, можна вважати, що i=1. Пофарбуємо

вершини x1, x2 зеленим кольором, а вершини x3, x4 ,.., xn пофарбуємо по

черзі жовтим та зеленим кольорами. Далі продовжимо розфарбування на S як

і у випадку парного числа n.

 

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((.

-----> Page:

0 [1]

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