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

(i) (1 (x) = (2 (f(x)) для всіх x(V1;

(ii) якщо (x,y)(E1, то (f(x), f(y))(E2.

Однорідне дерево Tr(V,E) степеня s з визначеним калейдоскопічним розфарбуванням (: V({0,1,…,s} множини його вершин називається вільним калейдоскопічним деревом степеня s.

Теорема 3. Нехай Tr(V,E) - вільне калейдоскопічне дерево степеня s з калейдоскопічним розфарбуванням (: V({0,1,…,s}, Gr1(V1,E1) - довільний калейдоскопічним граф степеня s з калейдоскопічним розфарбуванням (1: V1({0,1,…,s}. Тоді існує калейдоскопічний гомоморфізм f: V(V1.

Доведення. Зафіксуємо довільні вершини x (V, y(V1 для яких ((x)=(1(y) і покладемо f(x)=y. Для кожного невід'ємного цілого числа m позначимо Sm (x)={z(V: d(x,z)=m}. Припустимо, що відображення f вже визначене на множині S0(x)( S1(x)( …( Sm(x). Візьмемо довільну вершину z(Sm+1(x) і виберемо вершину z'(Sm(x) так, що d(z,z')=1. Далі виберемо вершину t(B(f(z'),1), для якої ((z')=(1(t). Покладемо f(z)=t. За побудовою f - калейдоскопічний гомоморфізм.

Нехай s - натуральне число >1, X={0,1,…,s}. Калейдоскопічна напівгрупа KS(X) в алфавіті X - це напівгрупа, визначена співвідношеннями xx=x, xyx=x для всіх x,y(X. Напівгрупу KS(X) зручно розглядати як множину усіх непорожніх слів в алфавіті X без факторів xx, xyx для всіх x,y(X.

Покажемо, що напівгрупа KS(X) діє транзитивно на множині вершин кожного калейдоскопічного графа Gr(V,E) степеня s з калейдоскопічним розфарбуванням (: V({0,1,…,s}. Візьмемо довільні x(X, v(V . Виберемо вершину u(B(v,1), для якої ((u)=x, і покладемо x(v)=u. Далі продовжимо індуктивно дію з множини X на KS(X) за таким правилом. Якщо w(KS(X), w=xw1 , w1(KS(X) і v(V, покладемо w(v)=x(w1(v)). Зауважимо, що послідовність кольорів вершин на найкоротшому шляху від вершини v1(V до вершини v2(V визначає слово w(KS(X), таке що w(v1)=v2. Звідси випливає, що визначена дія транзитивна.

Для кожного x(X підмножина KG(X,x) усіх слів з KS(X), що начинаються і закінчуються літерою x, є підгрупою напівгрупи KS(X) з одиницею x. Для того щоб одержати обернений елемент до слова w(KG(X,x) досить записати це слово у зворотному порядку. Назвемо KG(X,x) калейдоскопічною групою.

Для дослідження структури калейдоскопічних груп та напівгруп введемо допоміжні позначення.

Для нескорочуваного слова u(KS(X) позначимо через ( (u) та ( (u) першу та останню літери слова u. Якщо u=x1 x2…xn-1 xn, то позначимо через \x0169 слово xn xn-1 …x2 x1.

Лема 4. Нехай w1 w2(KS(X), ( (w2) =( (w1), w=w1 w2 і x1 x2…xn-1 xn - нескорочуваний запис слова w. Тоді знайдуться такі слово u(KS(X) і число k, що

w1=x1 x2…xk-1 u, w2 =\x0169 xk+1 xk+2…xn , u \x0169=xk .

Доведення. Оскільки ( (w2) =( (w1), то w1 =w1' x, w2 =x w2' для деякої літери x(X. Якщо ( (w1' ) (( (w2' ) то покладемо u=x. Якщо ( (w1' ) =( (w2' ), то w1' = w1'' y, w2'= y w2'' для деякої літери y(X. Застосуємо скорочення yxy=y і замінимо слова w1 , w2 словами w1' , w2' . Оскільки ці слова нескорочувані, то можна застосувати до них індуктивні міркування.

Нагадаємо, що елемент s напівгрупи S називається ідемпотентом, якщо ss=s.

Лема 5. Ідемоптентами напівгрупи KS(X) є всі слова x, xy, де x, y(X, x(y, і тільки вони.

Доведення. Очевидно, що всі слова x, xy є ідемпотентами. Нехай w - довільний ідемпотент напівгрупи KS(X). Припустимо, що ( (w)=( (w). За лемою 3.4

w=x1 x2…xk-1 u= \x0169 xk+1 …xn =x1 x2…xk xk+1 …xn ,

де x1 x2…xn - нескорочуваний запис слова w, u \x0169=xk . Звідси випливає що

u= xk xk+1 …xn , \x0169 =x1 x2…xk

Отже, u= xk xk-1 …x1 і w=x1 .

Припустимо, що ( (w)(( (w). Нехай ( (w)=x, w'=wx. Тоді

w'w'=wxwx=wwx=wx=w'.

Отже, w' - ідемпотент і ( (w')=( (w'). За доведеним вище w'=x. Значить, w=xy для деякого y(X.

Теорема 4. Група KG(X,x) є вільною групою з множиною вільних твірних

W={xyzx: y,z(X, x( y, x( z, y( z}.

Доведення. Нагадаємо, що одиницею групи KG(X,x) є x. Спочатку покажемо, що кожен неодиничний елемент g групи KG(X,x) можна записати у вигляді добутку елементів із W. Зауважимо, що W=W-1. Очевидно, що нескорочуваний запис елемента g факторизується на співмножники x x1 x2…xn x, n(2, x( xi, i({1,…,n} і серед сусідніх літер слова x1x2…xn немає однакових. Тоді

x x1 x2…xn-1 xn x=(x x1 x2 x)(x x2 x3 x)…(x xn-1 xn x).

Візьмемо довільне нескорочуване групове слово w1 w2…wn , n(1 в алфавіті і покажемо, що w1 w2…wn ( x. Для цього індукцією по числу n покажемо, що останні три літери в нескорочуваному записі слова w1 w2…wn як елемента напівгрупи KS(X) співпадають з останніми трьома літерами слова wn. Нехай wn-1=xabx, wn=xcdx. За припущенням індукції

w1 w2…wn-1 = x…abx.

Якщо c ( b, то