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

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

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


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Позначимо через I граф з множиною вершин N={1,2…} і множиною ребер E={(1,2),(2,3),…}. В цьому параграфі охарактеризовано кульові B структури графів і груп, для яких справедливе одне з таких співвідношень.

B B(I), B(I) B, B(I) B.

Нехай Gr1(V1,E1), Gr2(V2,E2) ─ графи, kN. Відображення f множини V1 на множину V2 називається k-домінантним, якщо B(f(x),1) f(B(x,k)) для кожного xV1. Лема 1 стверджує, що відображення f: V1 V2 є -відображенням кульової структури B(Gr1) на кульову структуру B(Gr2) тоді і тільки тоді, коли f ─ домінантне відображення для деякого kN.

Лема 1. Нехай Gr1(V1,E1), Gr2(V2,E2) ─ графи, kN, f ─ k-домінантне відображення V1 на V2 . Тоді B(f(x),m) f(B(x,km)) для всіх xV1, m.

Доведення. Зафіксуємо довільні xV1, m. Для елемента yB(f(x),m) виберемо елементи y1, y2, …, yn, ni+1.

Доведення. Припустимо, що B(I) B(Gr) і зафіксуємо -відображення f: N V. Виберемо натуральне число k так, що B(f(y),1) f(B(y,k)) для всіх yN. Покладемо m=2k+1 і розіб'ємо множину натуральних чисел N на послідовні відрізки A0, A1,… довжини m. Покладемо

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

Ясно, що |Vi| m і Vi Vi. Зафіксуємо i і візьмемо довільний елемент xVi. Виберемо aAi, для якого f(a)=x. Тоді

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

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

Припустимо, що існує розбиття V=i Vi і натуральне число m, що задовольняють припущенню леми. Визначимо бієкцію f: N V так, що з умов a,bN, a

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



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

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