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

-відображенням 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,(),( )( B(x,( ((,())

.

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

Доведення. Для кожної пари (,((P виберемо ( ((,() так, що B(B(x,(),()(B(x,( ((,()). Візьмемо довільний елемент z(B*(B*(x,(),() і виберемо елемент y(B*(x,() такий що z(B*(y,(). Тоді x(B(y,(), y(B(z,(). Отже, x(B(B(z,(),(). Оскільки B(B(z,(),()(B(z,(((,()), то x(B(z,(((,()). Отже, B*(B*(x,(),( )( 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),(1),( 2)( B2(f(x,())

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

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

B2(f(x),(1)( f (B1(x,(1), B2(f(x),( 2)( f(B1(x,(2))

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

Оскільки B1 мультиплікативна, то існує ((P1, таке що B1(B1(x,(1),(2 )( B1(x,() для кожного x(X1.

-відображення, то існує ( (P2, таке що f(B1(x,()) (B2(f(x),( ) для кожного x(X1.

Зафіксуємо x(X1 і візьмемо довільний елемент f(z)(B2(B2(f(x),(1),(2). Знайдемо f(y)(B2(f(x),(1) для якого f(z)( B2(f(y),(2). Тоді

y( B1(x,(1), z( B1(y,(2), z( B1(B1(x,(1),(2).

Отже, z( B1(x,() і f(z)( B2(f(x),().

Нагадаємо, що передпорядок ( на множині 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),()( 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 зв’язна, симетрична, мультиплікативна і