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

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),( 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),( 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),()

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

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

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

Зафіксуємо довільний елемент ((P2 і припустимо, що f(x)(B2(f(y),(), f(y)(B2(f(x),(). Оскільки 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-зв’язна.