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

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

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

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

 

ПОШУК:   

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

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

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

 

Розкладність графів. Комбінаторні розміри підмножин графів і груп

 

 

Застосуємо результати попереднього параграфу до кульових структур

графів і груп.

 

Теорема 1 Якщо множину вершин V довільно зв'язного графа Gr(V,E)

розбито на скінченне число підмножин V=V1( V2( …(Vn, то принаймні одна

підмножина Vi розбиття має таку властивість: існує натуральне число m,

таке що підмножина

 

{x(V: B(x,k)( B(Vi,m)}

 

непорожня для кожного натурального числа k.

 

Доведення. Розглянемо кульову структуру B(Gr) і, виберемо кусково велику

підмножину Vi розбиття.

 

Якщо Gr(V,E) ( звязний граф скінченного діаметра, то кожна

одноелементна підмножина {x}, x(V велика в кульовій структурі B(Gr),

еквівалентно, {x} має скінченний індекс. Отже, кожна підмножина

довільного розбиття V на непорожні множини велика. Перше твердження

наступної теореми показує, що це не можливо для графів нескінченного

діаметра.

 

Теорема 2. Для довільного звязного графа Gr(V,E) нескінченного діаметра

справедливі такі твердження

 

(і) множину V можна розбити на зліченне число малих підмножин;

 

(іі) множину V можна розбити на зліченне число великих підмножин.

 

Доведення. (і) Зафіксуємо довільну вершину x(V і покладемо S0(x)={x},

Sn+1(x)=B(x,n+1)\B(x,n), n ((. Оскільки Gr ( звязний граф нескінченного

діаметра, то Sn(x)(( для кожного n((. Очевидно, що V=(n(( Sn(x).

Покажемо, що кожна підмножина Sn(x) мала. Візьмемо довільне натуральне

число k і виберемо деяку вершину y(B(Sn(x),k). Позначимо через d

відстань від y до x. Тоді

 

B(Sn(x),k)(B(y, d+n+k)(B(V\B(Sn(x), k), d+n+k).

 

Отже, V=B(V\B(Sn(x), k), d+n+k).

 

(іі) Зафіксуємо пару натуральних чисел a, b і розглянемо нескінченну

арифметичну прогресію W={an+b: n((}. Покладемо L(W)=(n(( San+b(x) і

помітимо, що

 

B(x,b)(B(Sb(x),2b), B(x, a(n+1)+b)\B(x,an+b))(B(San+b(x),a)

 

для кожного n((. Отже, B(L(W), a+2b)=V і підмножина L(W) велика.

Розіб'ємо (=(i(( Wi на нескінченні арифметичні прогресії. Тоді V= (i((

L(Wi ) і {L(Wi ): i((} диз'юнктна сім'я великих підмножин.

 

Приклад 1. Для кожного нескінченного кардинала ( побудуємо зв'язний

граф Gr(V,E) нескінченного діаметра, такий що множину вершин V не можна

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

Gr'(V',E'), |V'|=(. Зафіксуємо довільний елемент x(V' і візьмемо

зліченну множину Y={yn: n((}, таку що Y(V'=(. Покладемо

 

V= V'(Y, E=E'({(x, y0)}({(yn, yn+1): n((}.

 

Досить помітити що кожна велика підмножина множини вершин V графа

Gr(V,E) містить деяку нескінченну підмножину множини Y.

 

Приклад 2. Для кожного нескінченного кардинала ( побудуємо зв'язний

граф Gr(V,E) нескінченного діаметра, такий що множину вершин V можна

розбити на ( великих підмножин. Візьмемо однорідне дерево локального

степеня (. Зафіксуємо довільну вершину x дерева і виберемо по одному

елементу з кожної підмножини Sn(x), n>0. Утвориться деяка підмножина L.

Очевидно, що B(L,1)=V, а тому підмножина L велика. Далі множину вершин

V легко розбити на ( підмножин цього типу.

 

За теоремою кульова структура B(Gr) довільного нескінченного звязного

-----> Page:

0 [1] [2]

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