WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Розкладність графів. Калейдоскопічні графи - Реферат

Розкладність графів. Калейдоскопічні графи - Реферат

За побудовою 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, то позначимо через ? слово 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 =? xk+1 xk+2…xn , u ?=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= ? xk+1 …xn =x1 x2…xk xk+1 …xn ,
де x1 x2…xn - нескорочуваний запис слова w, u ?=xk . Звідси випливає що
u= xk xk+1 …xn , ? =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, то
w1 w2…wn-1 wn= x…abxcdx
і це слово нескорочуване. Якщо b=c, то
w1 w2…wn-1 wn= x…acdx.
Оскільки b=c, то a c. Отже, якщо a d, то це слово нескорочуване. У випадку a=d маємо wn-1 = xdcx і wn= wn-1 -1, що суперечить припущенню про нескорочуваність w1 w2…wn-1 wn як групового слова в алфавіті W.
Для фіксованого елемента x X, X={0,1,…,s} позначимо L(x)={yx: y X}, R(x)={xy: y X}.
Теорема 5. Калейдоскопічна напівгрупа KS(X) ізоморфна сендвіч-добутку L(x) KG(X,x) R(x), в якому множення визначене за правилом
(l1, g1, r1)(l2, g2, r2)=(l1, g1 (r1, l2) g2, r2),
де (r1, l2)=r1, l2 .
Доведення. Кожен елемент x1 x2…xn KS(X) можна записати у вигляді
x1 x2…xn = x1 x ( x1 x2…xn) x xn= x1 x (x x1 x2…xnx) x xn .
Визначимо відображення f: KS(X) L(x) KG(X,x) R(x) за таким правилом
f (x1 x2…xn )=( x1 x, x x1 x2…xnx, x xn).
Для довільних елементів x1 x2…xn, y1 y2…ym KS(X) маємо
f (x1 x2…xn ) f(y1 y2…ym)=( x1 x, x x1 x2…xnx, x xn).
(y1 x, x y1 y2…ym x, xym)=( x1 x, x x1 …xnx (x xn , y1 x) xy1 …ym x, xym)=
= f(x1 x2…xn y1 y2…ym ).
Отже, бієкція f є ізоморфізмом між KS(X) та L(x) KG(X,x) R(x).
Розглянемо довільний однорідний граф Gr(V,E) нескінченного степеня k. За теоремою 2.3 існує розфарбування : V k, таке що кожна куля одиничного радіуса містить точки усіх k кольорів. Це означає, що буквальне поширення означення калейдоскопічності з однорідних графів скінченного степеня на однорідні графи нескінченного степеня беззмістовне. Одне із можливих означень таке.
Однорідний граф Gr(V,E) нескінченного степеня k називається калейдоскопічним, якщо існує розфарбування : V k, таке що
(і) кожна одинична куля містить точки усіх k кольорів;
(іі) в кожній одиничній кулі немає двох однокольорових точок.
Задача 1. Вказати приклад однорідного графа зліченного степеня, що не є калейдоскопічним.
Проблема характеризації калейдоскопічних графів однорідних графів нескінченного степеня вкладається в таку загальну проблему.
Проблема 1. Нехай X - нескінченна підмножина потужності k, - деяка сім'я її підмножин потужності k, | | k. Знайти умови, необхідні і достатні для існування розфарбування : V k, такого що кожна підмножина F містить і тільки одну точку кожного з k кольорів.
Loading...

 
 

Цікаве