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

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

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

Кульова структура — це трійка B=(X, P, B), де X, P — непорожні множини і для всіх x (X, ((P, B (x,() — підмножини множини X, що називається кулею радіуса (з центром в точці x. При цьому вимагається, щоб x (B (x,() для всіх x (X, ((P.

— відображенням, якщо для кожного ((P2 існує ((P1, таке що.

B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES () (f (B1(x,()).

B2.

— відображенням, якщо для кожного ((P1 існує ((P2, таке що.

f (B1(x,())(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ().

B2.

— відображенням. При цьому B1, B2 називаються ізоморфними. Якщо X1 = X2 і тотожне відображення f: X1(X2 є ізоморфізмом між B1 і B2, то кульові структури B1, B2 називаються еквівалентними.

Властивість P кульових структур називається кульовою властивістю, якщо кожна кульова структура, ізоморфна до деякої кульової структури з властивістю P, теж має цю властивість.

Приклад 1. Нехай (X, d) — метричний простір, R+={x (R: x (0}. Для всіх x (X, r (R+ покладемо.

Bd (x, r) = {y (X: d (x, y)(r}.

Кульову структуру (X, R+, Bd) позначимо B (x, d).

Приклад 2. Нехай Gr (V, E) — зв’язний граф. Для всіх x (X, r (R+ покладемо.

B (x, r) = {y (V: d (x, y)(r}.

Кульова структура (V, R+, B) позначається B (Gr).

Кульова структура B називається метризованою, якщо B ізоморфна кульовій структурі B (X, d) деякого метричного простору (X, d). Кульова структура B називається графовою, якщо B ізоморфна кульовій структурі B (Gr) деякого зв’язного графа Gr.

Спочатку ми дамо характеризацію метризованих кульових структур, а потім — графових кульових структур.

Кульова структура B=(X, P, B) називається зв’язною, якщо для будь-якої пари x, y (X існує ((P, таке що y (B (x,(), x (B (y,().

— відображення X1 на X2. Якщо B1 зв «язна, то B2 теж зв «язна.

— відображення, то існує ((P2, таке що f (B1(x,())(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES () для кожного x (X1. Значить, f (y) (B2(f (z); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (), f (z) (B2(f (y); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (). Оскільки f (X1)=X2, то B2 зв’язна.

— відображення X1 в X2. Якщо B1 зв’язна, то B2 теж зв’язна.

— відображення, то існує ((P1, таке що B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(f (B1(x,()) для кожного x (X1. Оскільки відображення f ін «єктивне, то y (B1(z,(), z (B1(y,(). Отже, B2 зв’язна.

Нехай B=(X, P, B) — довільна кульова структура. Для всіх x (X, ((P покладемо.

B*(x,()={y (X: x (B (y,()}.

Кульова структура B*=(X, P, B*) називається дуальною до B. Зауважимо, що B**=B.

Кульова структура B=(X, P, B) називається симетричною, якщо кульові структури B, B* еквівалентні. Отже, B симетрична тоді і тільки тоді, коли для кожного ((P існує ((P, таке що B (x,()(B*(x,(), і навпаки для кожного ((P існує ((P, таке що B*(x,()(B (x,().

— відображення B*1 в B*2. Якщо f — ізоморфізм між B1 і B2, то f — ізоморфізм між B*1 і B*2 .

— відображенням B*1 в B*2.

— відображенням B*2 в B*1. Отже, f-1 — ізоморфізм між B*1 і B*2 .

Лема 4. Нехай B1=(X1,P1,B1), B2=(X2,P2,B2) — ізоморфні кульові структури. Якщо B1 симетрична, то B2 теж симетрична.

Доведення. Позначимо через f1 ізоморфізм між B1 і B2. Позначимо через i1: X1(X1, i2: X2(X2 тотожні відображення. Очевидно, f -1 — ізоморфізм між B2 і B1. За лемою 7.3 f — ізоморфізм між B*1 і B*2. За припущенням леми i1 — ізоморфізм між B1 і B*1. Оскільки i2=f i1 f -1, то i2 — ізоморфізм між B2 і B*2 .

Кульова структура B=(X, P, B) називається мультиплікативною, якщо для будь-яких (,((P існує (((,()(P, таке що.

B (B (x,(); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(B (x,(((,()).

.

Лема 5. Якщо кульова структура B=(X, P, B) мультиплікативна, то B* теж мультиплікативна.

Доведення. Для кожної пари (,((P виберемо (((,() так, що B (B (x,(); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(B (x,(((,()). Візьмемо довільний елемент z (B*(B*(x,(); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES () і виберемо елемент y (B*(x,() такий що z (B*(y,(). Тоді x (B (y,(), y (B (z,(). Отже, x (B (B (z,(); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (). Оскільки B (B (z,(); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(B (z,(((,()), то x (B (z,(((,()). Отже, B*(B*(x,(); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(B*(x,(((,()) і B* мультиплікативна.

Лема 6. Нехай B1=(X1,P1,B1), B2=(X2,P2,B2) — ізоморфні кульові структури. Якщо B1 мультиплікативна, то B2 теж мультиплікативна.

Доведення. Позначимо через f: X1(X1 ізоморфізм між B1 і B2. Зафіксуємо довільні (1, (2 (P2. Оскільки f — бієкція, досить довести, що існує ((P2, таке що.

B2(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (1); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (2)(B2(f (x,()).

для кожного x (X1.

— відображення, то існують (1,(2(P1, такі що.

B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (1)(f (B1(x,(1), B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (2)(f (B1(x,(2)).

для кожного x (X1.

Оскільки B1 мультиплікативна, то існує ((P1, таке що B1(B1(x,(1); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (2)(B1(x,() для кожного x (X1.

— відображення, то існує ((P2, таке що f (B1(x,()) (B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES () для кожного x (X1.

Зафіксуємо x (X1 і візьмемо довільний елемент f (z)(B2(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (1); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (2). Знайдемо f (y)(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (1) для якого f (z)(B2(f (y); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (2). Тоді.

y (B1(x,(1), z (B1(y,(2), z (B1(B1(x,(1); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (2).

Отже, z (B1(x,() і f (z)(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ().

Нагадаємо, що передпорядок (на множині X — це бінарне відношення, для якого x (x і з x (y, y (z випливає, що x (z .

Для кульової структури B=(X, P, B) визначимо передпорядок (на множині P за таким правилом (((тоді і тільки тоді, коли B (x,()(B (x,() для кожного x (X. Підмножина P «(P називається конфінальною, якщо для кожного ((P існує ((P », таке що (((. Конфінальність cf B — це найменша потужність конфінальних підмножин множини P.

Кульова структура B=(X, P, B) називається напрямленою, якщо для будь-яких (, ((P існує ((P таке що (((, (((. Зауважимо, що кожна мультиплікативна кульова структура напрямлена. Крім того, конфінальність напрямленої структури ((0 тоді і тільки тоді, коли існує конфінальна в P послідовність <(n>n ((, така що (0((1(…((n (…

Лема 7. Якщо кульові структури B1=(X1,P1,B1), B2=(X2,P2,B2) ізоморфні, то cf B1=cf B2.

— відображенням, то існує відображення h1: P2(P «1, таке що.

B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ()(f (B1(x, h1(()).

— відображення, то існує відображення h2: P «1(P2, таке що.

f (B1(x,()(B2(f (x), h2(()).

для всіх x (X1, ((P «1. За визначенням відображень h1, h2 підмножина h2 (P «1) конфінальна в P «2. Отже, cf B2 (cf B1.

Теорема 1. Кульова структура B=(X, P, B) метризована тоді і тільки тоді, коли B зв’язна, симетрична, мультиплікативна і.

cf B ((0.

Доведення. Спочатку припустимо, що B ізоморфна кульовій структурі B=(X,() деякого метричного простору (X, d). Очевидно, що B (X, d) симетрична, зв’язна, мультиплікативна і cf B ((0. Враховуючи леми 1,4,6,7, можна стверджувати, що B має всі ці властивості.

Припустимо, що B зв’язна, симетрична, мультиплікативна і B ((0. Зафіксуємо довільну конфінальну в P послідовність <(n>n ((. Покладемо (0=(0 і виберемо (1(P так, що.

(1((1, (1((0, (1((((0, (0).

де (- функція з означення мультиплікативності. Припустимо, що ми вже вибрали елементи (0, (1,…, (n. Виберемо елемент (n+1(P так, що.

(n+1((n+1, (n+1((n, (n+1((((i, (j).

для всіх i, j ({0, 1, …, n}. Тоді <(n>n ((- неспадна конфінальна послідовність в P і.

B (B (x,(n); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (m)(B (x,(n+m).

для всіх x (X, n, m (N.

Визначимо відображення d: X (X ((за таким правилом: d (x, x)=0 і.

d (x, y)=min {n (N: y (B (x,(n), x (B (y,(n)}.

для всіх різних елементів x, y (X. Оскільки послідовність <(n>n ((конфінальна в P і B зв’язна, то відображення d визначено коректно. Для того, щоб переконатись у тому, що d — метрика, досить перевірити нерівність трикутника. Нехай x, y, z — різні елементи множини X, d (x, y)=n, d (y, z)=m. Оскільки, y (B (z,(m), x (B (y,(n) то x (B (B (z,(m); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (n)(B (z,(n+m). Звідси випливає, що d (x, z)(n+m.

Розглянемо кульову структуру B (X, d) і помітимо, що Bd (x, n)=B (x,(n)(B*(x,(n). Оскільки кульова B симетрична, то тотожне відображення множини X являється ізоморфізмом між B і B (X, d).

Зауважимо, що побудована метрика цілочисельна.

B (X, d).

— відображенням B (X, d) на B.

Для характеризації графових кульових структур введемо ще одне означення.

Нехай B=(X, P, B) — довільна кульова структура, ((P. Скінченна послідовність x0, x1, …, xn елементів множини X називається (-шляхом довжини n, якщо xi-1(B (xi,(), xi (B (xi-1,() для кожного i ({1,2,…, n}. Кульова структура B називається (- зв’язною, якщо для будь-якого ((P існує ((()((, таке що з x (B (y,(), y (B (x,() випливає існування (-шляху довжини (((() між x і y. Зауважимо, що B (Gr) 1-звязна для будь-якого зв’язного графа Gr.

Кульова структура B=(X, P, B) називається p-зв'язною, якщо B (-зв «язна для деякого ((P.

Лема 8. Нехай B1=(X1,P1,B1), B2=(X2,P2,B2) — ізоморфні кульові структури. Якщо B1 p-зв'язна, то B2 теж p-зв'язна.

— відображенням, то існує ((P2, таке що.

f (B1(x,())(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES ().

— відображенням, то існує відображення h: P2(P1., таке що.

B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES () (f (B1(x, h (()).

для всіх x (X1, ((P2.

Зафіксуємо довільний елемент ((P2 і припустимо, що f (x)(B2(f (y); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (), f (y)(B2(f (x); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (). Оскільки f-бієкція, то x (B1(y, h ((), y (B1(x, h ((). Оскільки B1 (-зв'язна, то існує (-шлях x=x0, x1,…, xm=y довжини ((h ((). Значить, f (x)=f (x0), f (x1), …, f (xm) (-шлях довжини ((h (() між f (x) і f (y).

Теорема 2. Для довільної кульової структури B наступні твердження еквівалентні.

(і) B метризована і p-зв'язна;

(іі) B графова.

Доведення. (іі) ((і). Нехай Gr — зв «язний граф. Очевидно, що кульова структура B (Gr) метризована і зв’язна. За лемою 8 будь-яка кульова структура, ізоморфна B (Gr) теж p-зв'язна.

(і) ((іi). Зафіксуємо p-зв'язний метричний простір (X, d), такий що B ізоморфна B (X, d). Виберемо m ((так, що простір (X, d) m-зв'язний. Розглянемо граф Gr (X, E) з множиною ребер E, визначеною за таким правилом (x, y)(E тоді і тільки тоді, коли x (y і d (x, y)(m. Оскільки кульова структура B (X, d) p-зв'язна, то граф Gr зв’язний.

Нехай d «- метрика на графі Gr. За припущенням, для кожного n ((існує ((n)((, таке що з умови d (x, y)(n випливає d «(x, y)(((n). З іншого боку, з умови d «(x, y)(k випливає d (x, y)(km. Значить, тотожне відображення множини X являється ізоморфізмом між кульовими структурами B (X, d) і B (Gr).

Задача 3. Навести приклад метричного простору (X, d), для якого кульова структура B (X, d) не є графовою.

Приклад 3. Для довільної групи G позначимо через Fine (G) сім «ю усіх скінченних підмножин групи G, що містять одиницю e групи. Для всіх x (G, F (Fine (G) покладемо.

Bl (x, F)=Fx, Br (x, F)=xF.

Кульові структури (G, Fine, Bl) і (G, Fine, Br) позначимо Bl (G) і Br (G). Очевидно, що відображення x (x-1 є ізоморфізмом між Bl (G) і Br (G). Надалі будь-яку з цих двох ізоморфних кульових структур позначаємо B (G). Зауважимо, що B (G) зв’язна, симетрична і мультиплікативна.

Теорема 3. Кульова структура B (G) групи G метризована тоді і тільки тоді, коли |G|((0.

Доведення випливає з теореми 7.1.

Теорема 4. Для довільної групи G наступні два твердження рівносильні:

(і) група G скінченно породжена;

(іі) кульова структура B (G) графова.

Доведення. (і) ((іi). Позначимо через S скінченну систему твірних групи G. Розглянемо граф Келі Gr (G, E) групи G, визначений системою твірних S (S-1. За означенням (x, y)(E тоді і тільки тоді, коли x (y і x=ty для деякого t (S (S-1. Очевидно, що тотожне відображення G (G є гомоморфізмом між B (G) і B (Gr) .

(іі) ((і). За теоремою 2 існує F (Fine (G), таке що B (G) є F-зв'язною. Зокрема, для кожного елемента g (G існує F-шлях від e до g. Це означає, що скінченна підмножина F породжує групу G.

Проблема 1. Охарактеризувати кульові структури, ізоморфні кульовим структурам груп.

З кожним орієнтовним графом Gr (V, E) природньо пов «язані дві.

(Gr)) — це множина усіх вершин y (V, для яких існує орієнтовний шлях від x до y (відповідно від y до x) довжини (m.

Проблема 2. Охарактеризувати кульові структури, ізоморфні кульовим структурам орієнтовних графів.