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

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

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

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

 

ПОШУК:   

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

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

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

 

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

 

Позначимо через I граф з множиною вершин N={1,2…} і множиною ребер

E={(1,2),(2,3),…}. В цьому параграфі охарактеризовано кульові B

структури графів і груп, для яких справедливе одне з таких

співвідношень.

 

B.

 

-відображенням кульової структури B(Gr1) на кульову структуру B(Gr2)

тоді і тільки тоді, коли f ? домінантне відображення для деякого k(N.

 

Лема 1. Нехай Gr1(V1,E1), Gr2(V2,E2) ? графи, k(N, f ? k-домінантне

відображення V1 на V2 . Тоді B(f(x),m)( f(B(x,km)) для всіх x(V1, m ((.

 

Доведення. Зафіксуємо довільні x(V1, m ((. Для елемента y(B(f(x),m)

виберемо елементи y1, y2, …, yn, n

yn=y і (yi, yi+1)(E2 для всіх i( n-1. За припущенням існують елементи

x1,x2,…,xn(V1, такі що x=x1, f(x1)=y1, f(x2)=y2,…, f(xn)=yn і d(xi,

xi+1)( k для всіх i( n-1 . Оскільки y=yn, n( m, то y(f(B(x,km)).

 

B(Gr2), то існує k((, таке що |B(y,m)|( g(km) для всіх y(V2, m ((.

 

-відображення B(Gr1) на B(Gr2). Виберемо k(( так, що B(f(x),1) (

f(B(x,k)) для всіх x(V1. За лемою 1 B(f(x),m)( f(B(x,km)) для всіх

x(V1. Отже, |B(f(x),m)|( g(k,m) для всіх x(V1, m ((. Оскільки f

відображає V1 на V2 , то |B(y,m)|( g(km) для всіх y(V2, m ((.

 

B(Gr) тоді і тільки тоді, коли існують розбиття V=(i(( Vi і натуральне

число m, такі що |Vi|( m і B(x,1)(Vj=( для всіх x(Vi, i (( і всіх

j>i+1.

 

-відображення f: N( V. Виберемо натуральне число k так, що B(f(y),1) (

f(B(y,k)) для всіх y(N. Покладемо m=2k+1 і розіб'ємо множину натуральних

чисел N на послідовні відрізки A0, A1,… довжини m. Покладемо

 

V0 =f(A0), V1 =f(A1)\V0 , V2=f(A2)\(V1(V2), ….

 

Ясно, що |Vi|( m і V=(i(( Vi. Зафіксуємо i(( і візьмемо довільний

елемент x(Vi. Виберемо a(Ai, для якого f(a)=x. Тоді

 

B(x,1) =B(f(a),1)( f(B(a,k))( f(Ai-1(Ai (Ai+1).

 

Отже, B(x,1) (Vj = ( для всіх j>i+1.

 

Припустимо, що існує розбиття V=(i(( Vi і натуральне число m, що

задовольняють припущенню леми. Визначимо бієкцію f: N( V так, що з умов

a,b(N, a

довільний елемент x(Vi. Виберемо a(N з f(a)=x. Тоді

 

B(f(a),1)=B(x,1) ( Vi-1(Vi(Vi+1 .

 

-відображення B(I) на B(Gr).

 

Нехай B(X,P,B) ? довільна кульова структура, ((P. Ін'єктивну

послідовність n(( елементів множини X назвемо (-променем, якщо xn+1

( B(xn,() для всіх n((.

 

B, то кожна диз'юнктна сім'я (-променів на множині X скінченна.

 

-відображення. Виберемо m(( так, що

 

(() B(f(y),()( f(B(y,m))

 

для всіх y(N. Нехай n(( (-промінь. Виберемо y0(N з f(y0)=x0.

Користуючись співвідношенням ((), побудуємо індуктивну послідовність

n(( в N, таку що f(yn)=xn і |yn+1 - yn|( m для всіх n((. Оскільки

послідовність n(( ін'єктивна, то відрізок [a,b](N довжини m, містить

точку e, таку що f(e)({xn: n((}. Звідси випливає, що кожна диз'юнктна

сім'я (-променів в X має потужність ( m.

 

Для довільної послідовності i(( натуральних чисел позначимо [ki]=

{1,2,…,ki}, i((. Прямим добутком X=(i(( [ki] називається множина усіх

-----> Page:

0 [1] [2] [3] [4]

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