Реферат на тему:
Розкладність графів. Калейдоскопічні графи
Однорідний граф Gr(V,E) скінченного степеня s називається
калейдоскопічним, якщо існує розфарбування (: V({0,1,(,s}, таке що
|((B(x,1))|=s+1 для будь-якого x(V. В цьому разі розфарбування ( теж
називається калейдоскопічним. Отже, калейдоскопічні графи – це графи, що
допускають калейдоскопічне розфарбування. Дамо рівносильне означення:
розфарбування (: V({0,1,(,s} називається калейдоскопічним, якщо в кожній
кулі одиничного радіуса немає двох однокольорових вершин.
З точки зору розкладності калейдоскопічні графи – це однорідні графи
скінченого степеня, максимально розкладні відносно сім’ї всіх одиничних
куль.
Розпочнемо дослідження калейдоскопічних графів з їх елементарних
властивостей та прикладів. Далі запис a|b означає, що ціле число a є
дільником цілого числа b.
Лема 1. Нехай Gr(V,E) – скінченний калейдоскопічний граф степеня s, (:
V({0,1,(,s} – калейдоскопічне розфарбування. Тоді справедливі такі
твердження:
s+1/n;
|(–1(0)|=|(–1(1)|=…=|(–1(s)|.
Доведення. Для кожного i({0,1,(,s} сім’я куль {B(x,1): x((–1(i)}
утворює розбиття множини вершин V. Оскільки |B(x,1)((–1(i)|=1 , то
(s+1)|(–1(i)|=|V|.
З цієї рівності випливають обидва твердження леми.
Приклад 1. Нехай Grn(Vn,En) – циклічний граф з n>2 вершинами. Припустимо
що Grn(Vn,En) калейдоскопічний. Оскільки Grn – однорідний граф степеня
2, то 3|n за лемою 3.1(і). З іншого боку, якщо 3/n, то періодичне
3-розфарбування множини Vn є калейдоскопічним.
Приклад 2. Розглянемо п’ять правильних многогранників у просторі як
скінченні графи і покажемо, що серед них калейдоскопічними є лише
тетраедр, куб та ікосаедр. Очевидно, що кожне 4-розфарбування множини
вершин тетраедра є калейдоскопічним. Зафіксуємо довільну вершину x куба
і довільне 4-розфарбування кулі B(x,1). Далі, кожну вершину y’ куба,
симетричну до деякої вершини y(B(x,1) відносно центра куба пофарбуємо
кольором вершини y. Одержимо калейдоскопічне розфарбування куба.
Аналогічне розфарбування виявляється калейдоскопічним і для ікосаедра.
Оскільки октаедр має 6 вершин і є однорідним степеня 4, то він не є
калейдоскопічним за лемою 3.1(і). Нарешті, додекаедр є однорідним графом
степеня 3. Візьмемо довільний п’ятикутник, що є гранню додекаедра. Для
будь-якого 4-розфарбування множини вершин додекаедра, знайдуться
принаймні дві однокольорові точки на вказаній грані. Отже, одинична куля
з центром в деякій вершині грані містить дві однокольорові вершини.
Лема 2. Нехай Gr(V,E) – скінчений однорідний граф степеня s, |V|=2m,
X(V. Припустимо, що існують розбиття V=V(0)(V(1), |V(0)|=|V(1)|=m і
натуральні числа p, q, для яких виконуються такі умови:
({B(x,1): x(X} =V;
(s+1)|X|=2m;
s+1=p+q, p>q;
якщо x(V(i), i({0,1}, то |B(x,1)(V(i)|=p, |B(x,1)((V\V(i)|=q.
Тоді |X(V(0)|=|X(V(1)|.
Доведення. Позначимо k0=|X(V(0)|, k1=|X(V(1)|. З умов (і), (іv)
випливають такі нерівності
pk0+qk1 ( m,
qk0+pk1 ( m.
Додамо ці нерівності і отримаємо p|X|+q|X| ( 2m. З умов (іі), (ііі)
випливає, що (p+q)|X|=2m. Отже, числа k0, k1 задовольняють систему
лінійних рівнянь.
px0+qx1 = m,
qx0+px1 = m.
.
Лема 3. Нехай Gr(V,E) – скінченний однорідний граф степеня s, |V|=nm, m,
n – натуральні числа ( 2, X(V. Припустимо, що існують розбиття V=V(0)(
V(1)(…( V(n-1), |V(0)|=|V(1)|=…=|V(n-1)|=m і натуральні числа p, q для
яких виконуються умови:
( {B(x,1): x(X} =V;
(s+1)|X|=nm;
s+1=p+2q, p>2q;
якщо x(V(i), i({0,1,..,n-1}, то
B(x,1)( V((i-1) mod n)( V(i mod n)( V((i+1) mod n),
|B(x,1)( V(i mod n)|=p,
|B(x,1)( V((i-1) mod n)|= |B(x,1)( V((i+1) mod n)|=q.
Тоді |X( V(0)|=|X( V(1)|=…=|X( V(n-1)|.
Доведення. Позначимо ki=|X( V(i)|, i({0,1,…,n-1}. З умов (і), (іv)
випливають такі нерівності
pk0+qkn-1+qk1( m,
pk1+qk0+qk2( m,
……………………..
pkn-2+qkn-3+qkn-1( m,
pkn-1+qkn-2+qk0( m.
Додамо всі ці нерівності і отримаємо p|X|+2q|X|( nm . З умов (іі), (ііі)
випливає, що (p+2q)|X|=nm. Звідси випливає, що числа k0, k1,…, kn-1
задовольняють систему лінійних рівнянь
.
Помітимо, що визначник ( матриці системи є циркулянтом. Отже (=f((0)
f((1)…f((n-1), де (0 , (1,…, (n-1 – комплексні корені рівняння zn=1,
f(x)=p+qx+qxn-1. Оскільки p>2q, то f((i)( 0 для всіх i({0,1,…,n-1}.
Отже, ця система має єдиний розв’язок.. З іншого боку, система має
очевидний розв’язок
.
Нагадаємо означення неорієнтованого графа Келі групи. Для довільної
непорожньої підмножини А групи G позначимо через найменшу підгрупу
групи G, що містить A. Нехай G – група з одиницею e, S(G, S=S-1 і G=.
Графом Келі Cay(G,S) групи G, визначеним системою твірних S називається
граф з множиною вершин G і множиною ребер E, де x,y(E тоді і тільки
тоді, коли x( y і x-1y(S. Якщо множина S скінченна e(S і |S|-1=s, то
Cay(G,S) – однорідний граф степеня s.
Приклад 3. Нехай
G=( , ( (2, ( (m , m>2, S={a,b,b-1,e}.
З геометричної точки зору граф Cay(G,S) є призмою з 2m вершинами.
Припустимо, що граф Cay(G,S) калейдоскопічний і покажемо, що 4|m. Згодом
(приклад 3.6) ми доведемо і обернене твердження.
. Оскільки V(0)= (X0 ( V(0))( (X1( V(0))( (X2( V(0))( (X3( V(0)) , то
4|m.
Приклад 4. Нехай
G=( , ( (n, ( (m , n, m>2, S={a, a-1, b, b-1,e}.
Припустимо, що граф Cay(G,S) калейдоскопічний і покажемо, що 5|m, 5|n.
Для того, щоб застосувати лему 3.3 покладемо
s=4, p=3, q=1, V=G, ={0,1,…,n-1}, V(i)={(i,x): x(},
i({0,1,…,n-1}. Зафіксуємо калейдоскопічне розфарбування (: V({0,1,2,3,4}
і позначимо Xj= ( -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}.
, то 5|m. Аналогічно доводиться, що 6|n.
Перший метод побудови калейдоскопічних графів базується на такому
означенні.
Розглянемо групу G з одиницею e. Нехай X, Y ( G. За означенням (X,Y)
називається калейдоскопічною парою, якщо множина X скінченна і
виконуються такі умови
e(X, X=X-1, G=
e(Y, G=XY;
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=
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=
Хеммінгова пара.
Приклад 7. Нехай G=(, ( (5, ( (5, S={e,a,a-1,b,b-1}.
Покажемо, що Cay(G,S) – Хеммінговий граф. Покладемо H=
H=
Приклад 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=
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), x
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. За побудовою 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 кольорів.
Нашли опечатку? Выделите и нажмите CTRL+Enter
