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

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

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

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

-1 (j), j {0,1,2,3,4}. З леми 3.3 випливає
|Xj V(0)|=|Xj V(1)|=…=|Xj V(n-1)|, j {0,1,2,3,4}.
За лемою 3.1(іі), |Xj |= , j {0,1,2,3,4}. Оскільки V(0)= , то 5|m. Аналогічно доводиться, що 6|n.
Перший метод побудови калейдоскопічних графів базується на такому означенні.
Розглянемо групу G з одиницею e. Нехай X, Y G. За означенням (X,Y) називається калейдоскопічною парою, якщо множина X скінченна і виконуються такі умови
(i) e X, X=X-1, G=;
(ii) e Y, G=XY;
(iii) x-1XXx YY-1=e для всіх x X.
З умов (іі), (ііі) випливає, що XX YY-1={e}. Враховуючи умову (іі), можна стверджувати, що кожен елемент g G однозначно розкладається у добуток g=xy, x X, y Y.
Для калейдоскопічної пари (X,Y) визначимо стандартне розфарбування : G X за таким правилом. Для кожного x X покладемо (x)=x. Візьмемо довільний елемент g G і виберемо x X, y Y так, що g=xy. Покладемо (g)=x. Переконаємось у тому, що стандартне розфарбування множини вершин графу Cay(G,X) є калейдоскопічним.
Нехай g1,g2,g G , g1,g2 B(g,1) і (g1)= (g2). Переконаємося, що g1=g2. Виберемо x1,x2 X , y1,y2 Y так, що g1=x1y1, g2=x2y2.Оскільки (g1)=x1 , (g2)=x2 і (g1)= (g2), то x1=x2. Оскільки g1,g2 B(g,1) , то існують елементи z1,z2 X, такі що g1=z1g, g2=z2 g. Таким чином, x1y1=z1g, x1y2=z2g і z1-1 x1 y1=z2-1 x1 y2. Звідси випливає, що x1-1 z2 z1-1 x1 =y2y1-1. З умови (ііі) означення калейдоскопічної пари випливає, що x1-1 z2 z1-1 x1 =e. Отже,.z1=z2 і g1=g2.
Таким чином, ми довели таке твердження.
Теорема 1. Якщо (X,Y) - калейдоскопічна пара в групі G, то Cay(G,X) - калейдоскопічний граф.
Калейдоскопічна пара (X,Y) називається Хеммінговою парою, якщо Y - підгрупа групи G. В цьому випадку граф Cay(G,X) називається Хеммінговим графом.
Це означення обґрунтовується в прикладі 3.5.
Теорема 2. Нехай (X,Y) - калейдоскопічна пара в групі G, - стандартне розфарбування групи G. Тоді такі два твердження рівносильні
(і) (X,Y) - Хеммінгова пара;
(іі) якщо g1,g2 G , x X і (g1)= (g2), то (x g1)= (x g2).
Доведення. (і)==>(іі). Виберемо y1,y2 Y і a X так, що g1=ay1, g2=ay2. Далі виберемо z1,z2 Y і b1,b2 X так, щоб виконувались рівності xg1=b1z1, xg2=b2z2. Тоді z1=b1-1xay1, z2=b2-1xay2. Оскільки Y - підгрупа групи G, то b1-1xa Y , b2-1xa Y , b1-1b2 Y. З умови (ііі) означення калейдоскопічної пари випливає b1=b2. Отже, (x g1)= (x g2).
(іі)==>(і). Нехай y1,y2 Y . Тоді (y1)= (y2)= (e)=e. З умови (іі) випливає, що (y1y2)= (y1e)=e, (y1-1y1)= (e)= (y1-1e)= (y1-1). Отже, y1y2 Y , y1-1 Y .
Приклад 5. Нехай G= … , 2, i {1,…,n}, S={e, x1,a2,…,an}. Припустимо, що куб Cay(G,S) є калейдоскопічним графом. За лемою 3.1(і), n+1|2n . З іншого боку, якщо n+1|2n , то існує підгрупа H групи G, така що сім'я {Sh: h H} є розбиттям групи G [2, §8.7]. Ця підгрупа H називається кодом Хеммінга. Очевидно, що (S,H)- Хеммінгова пара, а отже, Cay(G,S) - Хеммінговий граф.
Приклад 6. Нехай G= , 2, m, m>2. Припустимо, що 4|m і покажемо, що Cay(G,S) є Хеммінговим графом, де S={e, a, b, b-1}. Покладемо H=. Тоді H= {akb2k: k {1,3,…,m-1}}. Значить, (S,H) - Хеммінгова пара.
Приклад 7. Нехай G= , 5, 5, S={e,a,a-1,b,b-1}. Покажемо, що Cay(G,S) - Хеммінговий граф. Покладемо H=. Тоді H= і S-1S H={e}, SH=G.
Приклад 8. Нехай G= , , , S={e,a,a-1,b,b-1}. Покажемо, що Cay(G,S) - Хеммінговий граф. Помітимо, що
SS={e,a,a-1,b,b-1, a2,b2, a-2, b-2, ab, a-1b-1 , a-1b, ab-1}
і покладемо H=. Безпосередня перевірка дає SH=G, SS H={e}.
Зауважимо, що цей граф можна розглядати як квадратну мозаїку на площині. Аналогічно визначаються калейдоскопічні розфарбування для трикутних і шестикутних мозаїк на площині.
Викладемо другий метод побудови калейдоскопічних графів на основі графів Келі Cay(G,S) груп при деяких обмеженнях на множину твірних S.
Крок 1. Нехай G - група з одиницею e, S - скінченна підмножина групи, G=, e S, S=S-1. Припустимо також, що |S|=r(r-1) для деякого натурального числа r>1 і S не містить елементів порядку 2. Побудуємо розбиття S=S1 S2 … Sr, таке що |Si|=r-1, i {1,2,…,r} i |Si-1 Sj|=1 для всіх різних індексів i,j {1,2,…,r}. Для цього розіб'ємо множину S=A B так, що B=A-1. Таке розбиття можливе, оскільки S не містить елементів порядку 2. Виберемо довільні елементи x1,x2,…,xr-1 A і покладемо S1={x1,x2,…,xr-1}. Віднесемо елементи x1-1,x2-1,…, xr-1-1 до майбутніх підмножин S2, S3,…, Sr.Виберемо довільні елементи y2, y3,…, yr-1 A{x1,x2,…,xr-1}. Покладемо S2={x1-1,y2,y3,…,yr-1} і віднесемо елементи y2-1, y3-1,…, yr-1-1 до майбутніх підмножин S3, S4…, Sr. Виберемо довільні елементи
z3, z4, …, zr-1 A{x1,x2,…, xr-1, y2, y3,…, yr-1 },
покладемо S3={x2-1,y2-1,z3,…,zr-1}, віднесемо елементи z3-1, z4-1, …, zr-1-1 до майбутніх підмножин S4, S5,…, Sr і т. д.
Крок 2. Впорядкуємо групу G лінійно і ототожнимо кожне ребро графа Келі Cay(G,S) з парою (x,y), x1, 1: V1 {0,1,…,s}, 2: V2 {0,1,…,s}- їх калейдоскопічні розфарбування. Відображення f множини V1 на множину V2 називається калейдоскопічним гомоморфізмом, якщо
(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.
Loading...

 
 

Цікаве