Розкладність графів. Кульові структури, Детальна інформація

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

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

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

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

B2(f(x),() ( f(B1(x,())

B2.

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

f(B1(x,())(B2(f(x),()

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),() для кожного x(X1. Значить, f(y) ( B2(f(z),(), f(z) ( B2(f(y),(). Оскільки f(X1)=X2 , то B2 зв’язна.

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

-відображення, то існує ((P1, таке що B2(f(x),()(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.