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

Реферат на тему:

Розкладність графів. Калейдоскопічні графи Однорідний граф Gr (V, E) скінченного степеня s називається калейдоскопічним, якщо існує розфарбування 1, таке що |x, 1))|=s+1 для будь-якого xВ цьому разі розфарбування еж називається калейдоскопічним. Отже, калейдоскопічні графи — це графи, що допускають калейдоскопічне розфарбування. Дамо рівносильне означення: розфарбування 1, називається калейдоскопічним, якщо в кожній кулі одиничного радіуса немає двох однокольорових вершин.

З точки зору розкладності калейдоскопічні графи — це однорідні графи скінченого степеня, максимально розкладні відносно сім'ї всіх одиничних куль.

Розпочнемо дослідження калейдоскопічних графів з їх елементарних властивостей та прикладів. Далі запис a|b означає, що ціле число a є дільником цілого числа b.

Лема 1. Нехай Gr (V, E) — скінченний калейдоскопічний граф степеня s, 1, — калейдоскопічне розфарбування. Тоді справедливі такі твердження:

1. (i)s+1/n;

2. (ii)|(0)|=|(1)|=…=|(s)|.

Доведення. Для кожного i1, сім'я куль {B (x, 1): x—1(i)} утворює розбиття множини вершин V. Оскільки |B (x, 1)—1(i)|=1, то.

(s+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, 1) відносно центра куба пофарбуємо кольором вершини y. Одержимо калейдоскопічне розфарбування куба. Аналогічне розфарбування виявляється калейдоскопічним і для ікосаедра. Оскільки октаедр має 6 вершин і є однорідним степеня 4, то він не є калейдоскопічним за лемою 3.1(і). Нарешті, додекаедр є однорідним графом степеня 3. Візьмемо довільний п’ятикутник, що є гранню додекаедра. Для будь-якого 4-розфарбування множини вершин додекаедра, знайдуться принаймні дві однокольорові точки на вказаній грані. Отже, одинична куля з центром в деякій вершині грані містить дві однокольорові вершини.

Лема 2. Нехай Gr (V, E) — скінчений однорідний граф степеня s, |V|=2m, XПрипустимо, що існують розбиття V=V (0)), |V (0)|=|V (1)|=m і натуральні числа p, q, для яких виконуються такі умови:

1. (i)x, 1): x=V;

2. (ii)(s+1)|X|=2m;

3. (iii)s+1=p+q, p>q;

4. (iv)якщо x), i1}, то |B (x, 1))|=p, |B (x, 1) V (i)|=q.

Тоді |X)|=|X)|.

Доведення. Позначимо k0=|X)|, k1=|X)|. З умов (і), (іv) випливають такі нерівності.

pk0+qk1.

qk0+pk1.

Додамо ці нерівності і отримаємо p|X|+q|X|. З умов (іі), (ііі) випливає, що (p+q)|X|=2m. Отже, числа k0, k1 задовольняють систему лінійних рівнянь.

px0+qx1 = m,.

qx0+px1 = m.

Оскільки p>q, ця система має єдиний розв’язок. З іншого боку, система має очевидний розв’язок x0=x1= $$\frac{m}{p+q}$$ .

Лема 3. Нехай Gr (V, E) — скінченний однорідний граф степеня s, |V|=nm, m, n — натуральні числа XПрипустимо, що існують розбиття V=V (0)1)n-1), |V (0)|=|V (1)|=…=|V (n-1)|=m і натуральні числа p, q для яких виконуються умови:

1. (i)(x, 1): x=V;

2. (ii)(s+1)|X|=nm;

3. (iii)s+1=p+2q, p>2q;

4. (iv)якщо x), i1,., n-1}, то.

B (x, 1)(i-1) mod n) i mod n)(i+1) mod n),.

|B (x, 1) i mod n)|=p,.

|B (x, 1)(i-1) mod n)|= |B (x, 1)(i+1) mod n)|=q.

Тоді |X0)|=|X1)|=…=|Xn-1)|.

Доведення. Позначимо ki=|Xi)|, i1,…, n-1}. З умов (і), (іv) випливають такі нерівності.

pk0+qkn-1+qk1.

pk1+qk0+qk2.

…

pkn-2+qkn-3+qkn-1.

pkn-1+qkn-2+qk0.

Додамо всі ці нерівності і отримаємо p|X|+2q|X|. З умов (іі), (ііі) випливає, що (p+2q)|X|=nm. Звідси випливає, що числа k0, k1,…, kn-1 задовольняють систему лінійних рівнянь.

$$\left(\begin{array}{cccccccc}p& q& 0& 0& \text{.}\text{.}\text{.}& 0& 0& q\\ q& p& q& 0& \text{.}\text{.}\text{.}& 0& 0& 0\\ 0& q& p& q& \text{.}\text{.}\text{.}& 0& 0& 0\\ \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}& \text{.}\text{.}\text{.}\\ 0& 0& 0& 0& \text{.}\text{.}\text{.}& q& p& q\\ q& 0& 0& 0& \text{.}\text{.}\text{.}& 0& q& p\end{array}\right)$$ $$\left(\begin{array}{c}{x}_0\\ x_1\\ x_2\\ \text{.}\text{.}\text{.}\\ \begin{array}{c}{x}_{n-2}\\ x_{n-1}\end{array}\hfill \end{array}\right)$$ = $$\left(\begin{array}{c}m\\ m\\ m\\ \text{.}\text{.}\text{.}\\ \begin{array}{c}m\\ m\end{array}\hfill \end{array}\right)$$ .

Помітимо, що визначник атриці системи є циркулянтом. Отже f (…f (), де …, — комплексні корені рівняння zn=1, f (x)=p+qx+qxn-1. Оскільки p>2q, то f (для всіх i1,…, n-1}. Отже, ця система має єдиний розв’язок. З іншого боку, система має очевидний розв’язок.

x0=x1=…=xn-1= $$\frac{m}{p+2q}$$ .

Нагадаємо означення неорієнтованого графа Келі групи. Для довільної непорожньої підмножини, А групи G позначимо через <A> найменшу підгрупу групи G, що містить A. Нехай G — група з одиницею e, SS=S-1 і G=<S>. Графом Келі Cay (G, S) групи G, визначеним системою твірних S називається граф з множиною вершин G і множиною ребер E, де x, yтоді і тільки тоді, коли xі x-1yЯкщо множина S скінченна eі |S|-1=s, то Cay (G, S) — однорідний граф степеня s.

Приклад 3. Нехай.

G=<a>t-b>, <a> <b> m>2, S={a, b, b-1,e}.

З геометричної точки зору граф Cay (G, S) є призмою з 2m вершинами. Припустимо, що граф Cay (G, S) калейдоскопічний і покажемо, що 4|m. Згодом (приклад 3.6) ми доведемо і обернене твердження.

Для того, щоб застосувати лему 3.2 покладемо s=3, p=3, q=1, V=G, <a>={0,1}, V (0)={(0,x): x-b>}, V (1)={(1,x): x-b>}. Зафіксуємо калейдоскопічне розфарбування 1,2,3} і позначимо Xi=(i), i1,2,3}.За лемою 3.2, |Xi0)|= |Xi1)| для всіх i1,2,3}. За лемою 3.1(іі), |Xi|= $$\frac{m}{2}$$. Оскільки V (0)= (X0 0))10))20))30)), то 4|m.

Приклад 4. Нехай.

G=<a>t-b>, <a> <b> 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, <a>={0,1,…, n-1}, V (i)={(i, x): x-b>}, i1,…, n-1}. Зафіксуємо калейдоскопічне розфарбування 1,2,3,4} і позначимо Xj= (j), j1,2,3,4}. З леми 3.3 випливає.

|Xj 0)|=|Xj 1)|=…=|Xj n-1)|, j1,2,3,4}.

За лемою 3.1(іі), |Xj |= $$\frac{\text{nm}}{5}$$, j1,2,3,4}. Оскільки V (0)= $$\underset{j=0}{\overset{4}{}}(X_{j}V(0))$$, то 5|m. Аналогічно доводиться, що 6|n.

Перший метод побудови калейдоскопічних графів базується на такому означенні.

Розглянемо групу G з одиницею e. Нехай X, Y За означенням (X, Y) називається калейдоскопічною парою, якщо множина X скінченна і виконуються такі умови.

1. (i)eX=X-1, G=<X>;

2. (ii)eG=XY;

3. (iii)x-1XXx -1=e для всіх x.

З умов (іі), (ііі) випливає, що XX -1={e}. Враховуючи умову (іі), можна стверджувати, що кожен елемент gоднозначно розкладається у добуток g=xy, xy/p>

Для калейдоскопічної пари (X, Y) визначимо стандартне розфарбування за таким правилом. Для кожного xпокладемо =x. Візьмемо довільний елемент gі виберемо xyтак, що g=xy. Покладемо =x. Переконаємось у тому, що стандартне розфарбування множини вершин графу Cay (G, X) є калейдоскопічним.

Нехай g1, g2,g g1, g2g, 1) і)=). Переконаємося, що g1=g2. Виберемо x1, x2 y1, y2так, що g1=x1y1, g2=x2y2.Оскільки)=x1 ,)=x2 і)=), то x1=x2. Оскільки g1, g2g, 1), то існують елементи z1, z2такі що g1=z1g, g2=z2 g. Таким чином, x1y1=z1g, x1y2=z2g і z1−1×1 y1=z2−1×1 y2. Звідси випливає, що x1−1 z2 z1−1×1 =y2y1−1. З умови (ііі) означення калейдоскопічної пари випливає, що x1−1 z2 z1−1×1 =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 xі)=), то g1)=g2).

Доведення. (і)і). Виберемо y1, y2і aтак, що g1=ay1, g2=ay2. Далі виберемо z1, z2і b1, b2так, щоб виконувались рівності xg1=b1z1, xg2=b2z2. Тоді z1=b1−1xay1, z2=b2−1xay2. Оскільки Y — підгрупа групи G, то b1−1xa b2−1xa b1−1b2З умови (ііі) означення калейдоскопічної пари випливає b1=b2. Отже, g1)=g2).

(іі)). Нехай y1, y2 Тоді)=)==e. З умови (іі) випливає, що 1y2)=1e)=e, 1−1y1)=)=1−1e)=1−1). Отже, y1y2 y1−1.

Приклад 5. Нехай G=<a1>-a2>-an>, <ai>i…, n}, S={e, x1, a2,…, an}. Припустимо, що куб Cay (G, S) є калейдоскопічним графом. За лемою 3.1(і), n+1|2n. З іншого боку, якщо n+1|2n, то існує підгрупа H групи G, така що сім'я {Sh: hє розбиттям групи G [2, § 8.7]. Ця підгрупа H називається кодом Хеммінга. Очевидно, що (S, H) — Хеммінгова пара, а отже, Cay (G, S) — Хеммінговий граф.

Приклад 6. Нехай G=<a>-b>, <a><b>m>2. Припустимо, що 4|m і покажемо, що Cay (G, S) є Хеммінговим графом, де S={e, a, b, b-1}. Покладемо H=<ab2>. Тоді H=<b4>b2k: k3,…, m-1}}. Значить, (S, H) — Хеммінгова пара.

Приклад 7. Нехай G=<a>-b>, <a><b>S={e, a, a-1,b, b-1}. Покажемо, що Cay (G, S) — Хеммінговий граф. Покладемо H=<a3b>. Тоді H=<a3b, ab2, a4b3, a2b4> і S-1Se}, SH=G.

Приклад 8. Нехай G=<a>-b>, <a>lt-b>={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=<a2b2, a-2, b2>. Безпосередня перевірка дає SH=G, SSe}.

Зауважимо, що цей граф можна розглядати як квадратну мозаїку на площині. Аналогічно визначаються калейдоскопічні розфарбування для трикутних і шестикутних мозаїк на площині.

Викладемо другий метод побудови калейдоскопічних графів на основі графів Келі Cay (G, S) груп при деяких обмеженнях на множину твірних S.

Крок 1. Нехай G — група з одиницею e, S — скінченна підмножина групи, G=<S>, eS=S-1. Припустимо також, що |S|=r (r-1) для деякого натурального числа r>1 і S не містить елементів порядку 2. Побудуємо розбиття S=S1 таке що |Si|=r-1, i2,…, r} i |Si-1 |=1 для всіх різних індексів i, j2,…, r}. Для цього розіб'ємо множину S=Aтак, що B=A-1. Таке розбиття можливе, оскільки S не містить елементів порядку 2. Виберемо довільні елементи x1, x2,…, xr-1і покладемо S1={x1,x2,…, xr-1}. Віднесемо елементи x1−1,x2−1,…, xr-1−1 до майбутніх підмножин S2, S3,…, Sr. Виберемо довільні елементи y2, y3,…, yr-1×1,x2,…, xr-1}. Покладемо S2={x1−1,y2,y3,…, yr-1} і віднесемо елементи y2−1, y3−1,…, yr-1−1 до майбутніх підмножин S3, S4…, Sr. Виберемо довільні елементи.

z3, z4, …, zr-1×1,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<y. Позначимо через N потужність множини ребер графа Cay (G, S). Візьмемо довільну множину W потужності 2N, W побудуємо допоміжний граф Gr (G E). Для кожного ребра (x, y) графа Cay (G, S) виберемо різні елементи z, tі замінимо ребро (x, y) на шлях x, z, t, y. Занесемо ребра (x, zy), (z, t), (t, y) до E. При цьому, якщо (x, y) і (xрізні ребра графа Cay (G, S) і (x, y), (xзамінимо шляхами x, z, t, y і xо {z, t}p>

Крок 3. Визначимо розфарбування 2,…, r} за таким правилом. Покладемо =0 для всіх gНехай x, yі ребро (x, y) графа Cay (G, S) замінено на шлях x, z, t, y. Тоді x-1y=s, s Виберемо i, j2,…, r} так, що s, s-1. Покладемо =i, =j.

Крок 4. Для кожного xі кожного i2,…, r} існує рівно r-1 вершин z1, z2, …, zr-1 для яких (x, z1), (x, z2), …, (x, zr-1)і)=)= …=-1)=i. Склеїмо ці вершини в одну вершину, а ребра (x, z1), (x, z2), …, (x, zr-1) — в одне ребро. Після такої факторизації ми отримаємо калейдоскопічний граф.

Розглянемо деякі алгебраїчні конструкції, що природно виникають при дослідженні калейдоскопічних графів.

Нехай Gr1(V1,E1), Gr2(V2,E2) — калейдоскопічні графи степеня s>1, V11,…, s}, V21,…, s}- їх калейдоскопічні розфарбування. Відображення f множини V1 на множину V2 називається калейдоскопічним гомоморфізмом, якщо.

(i) x) = f (x)) для всіх x.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

w=x1 x2… xk-1 u= ~u xk+1 …xn =x1 x2… xk xk+1 …xn ,.

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

u= xk xk+1 …xn, ~u =x1 x2… xk.

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

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

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

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

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

W={xyzx: y, zx x y.

Доведення. Нагадаємо, що одиницею групи KG (X, x) є x. Спочатку покажемо, що кожен неодиничний елемент g групи KG (X, x) можна записати у вигляді добутку елементів із W. Зауважимо, що W=W-1. Очевидно, що нескорочуваний запис елемента g факторизується на співмножники x x1 x2… xn x, nx, i…, 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в алфавіті і покажемо, що w1 w2… wn Для цього індукцією по числу n покажемо, що останні три літери в нескорочуваному записі слова w1 w2… wn як елемента напівгрупи KS (X) співпадають з останніми трьома літерами слова wn. Нехай wn-1=xabx, wn=xcdx. За припущенням індукції.

w1 w2… wn-1 = x… abx.

Якщо c то.

w1 w2… wn-1 wn= x… abxcdx.

і це слово нескорочуване. Якщо b=c, то.

w1 w2… wn-1 wn= x… acdx.

Оскільки b=c, то aОтже, якщо aто це слово нескорочуване. У випадку a=d маємо wn-1 = xdcx і wn= wn-1 -1, що суперечить припущенню про нескорочуваність w1 w2… wn-1 wn як групового слова в алфавіті W.

Для фіксованого елемента xX={0,1,…, s} позначимо L (x)={yx: y R (x)={xy: y.

Теорема 5. Калейдоскопічна напівгрупа KS (X) ізоморфна сендвіч-добутку L (x)X, x)), в якому множення визначене за правилом.

(l1, g1, r1)(l2, g2, r2)=(l1, g11, l2) g2, r2),.

де 1, l2)=r1, l2 .

Доведення. Кожен елемент x1 x2… xnX) можна записати у вигляді.

x1 x2… xn = x1 x (x1 x2… xn) x xn= x1 x (x x1 x2… xnx) x xn .

Визначимо відображення f: KS (X) x) X, x)) за таким правилом.

f (x1 x2… xn)=(x1 x, x x1 x2… xnx, x xn).

Для довільних елементів x1 x2… xn, y1 y2… ym 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 xn, y1 x) xy1… ym x, xym)=.

= f (x1 x2… xn y1 y2… ym).

Отже, бієкція f є ізоморфізмом між KS (X) та L (x)X, x)).

Розглянемо довільний однорідний граф Gr (V, E) нескінченного степеня k. За теоремою 2.3 існує розфарбування таке що кожна куля одиничного радіуса містить точки усіх k кольорів. Це означає, що буквальне поширення означення калейдоскопічності з однорідних графів скінченного степеня на однорідні графи нескінченного степеня беззмістовне. Одне із можливих означень таке.

Однорідний граф Gr (V, E) нескінченного степеня k називається калейдоскопічним, якщо існує розфарбування таке що.

(і) кожна одинична куля містить точки усіх k кольорів;

(іі) в кожній одиничній кулі немає двох однокольорових точок.

Задача 1. Вказати приклад однорідного графа зліченного степеня, що не є калейдоскопічним.

Проблема характеризації калейдоскопічних графів однорідних графів нескінченного степеня вкладається в таку загальну проблему.

Проблема 1. Нехай X — нескінченна підмножина потужності k, деяка сім'я її підмножин потужності k, | Знайти умови, необхідні і достатні для існування розфарбування такого що кожна підмножина Fмістить і тільки одну точку кожного з k кольорів.