Головна Головна -> Реферати українською -> Математика -> Розкладність графів. Комбінаторні розміри підмножин графів і груп

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

Назва:
Розкладність графів. Комбінаторні розміри підмножин графів і груп
Тип:
Реферат
Мова:
Українська
Розмiр:
12,05 KB
Завантажень:
26
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Застосуємо результати попереднього параграфу до кульових структур графів і груп.

Теорема 1 Якщо множину вершин V довільно зв'язного графа Gr(V,E) розбито на скінченне число підмножин V=V1 V2Vn, то принаймні одна підмножина Vi розбиття має таку властивість: існує натуральне число m, таке що підмножина

{xV: 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 можна розбити на зліченне число великих підмножин.

Доведення. (і) Зафіксуємо довільну вершину xV і покладемо 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 і виберемо деяку вершину yB(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)= 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 L(Wi ) і {L(Wi ): i} диз'юнктна сім'я великих підмножин.

Приклад 1. Для кожного нескінченного кардинала побудуємо зв'язний граф Gr(V,E) нескінченного діаметра, такий що множину вершин V не можна розбити на незліченне число великих підмножин. Візьмемо повний граф Gr'(V',E'), |V'|. Зафіксуємо довільний елемент xV' і візьмемо зліченну множину 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) довільного нескінченного звязного локального скінченного графа Gr -розкладна відносно сім'ї всіх великих підмножин графа. Поширимо це твердження на довільні графи нескінченного діаметра.

Теорема 3. Множину V вершин довільного звязного графа Gr(V,E) нескінченного діаметра можна розбити на зліченне число підмножин V= i Ai так, що жодне з підмножин V\Ai не є великою. Зокрема, існує розбиття V=V1V2, таке що підмножини V1, V2 не є великими.

Доведення. Зафіксуємо довільний елемент x0V. Припустимо, що елементи x0, x1, …, xn вже вибрано так, що B(xi,i)B(xj,j)=, 0 i

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок