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

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

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

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


Реферат на тему:
Розкладність графів. Калейдоскопічні графи
Однорідний граф 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} - калейдоскопічне розфарбування. Тоді справедливі такі твердження:
(i) s+1/n;
(ii) | --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, для яких виконуються такі умови:
(i) {B(x,1): x X} =V;
(ii) (s+1)|X|=2m;
(iii) s+1=p+q, p>q;
(iv) якщо x V(i), i {0,1}, то |B(x,1) V(i)|=p, |B(x,1) (VV(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.
Оскільки p>q, ця система має єдиний розв'язок. З іншого боку, система має очевидний розв'язок x0=x1= .
Лема 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 для яких виконуються умови:
(i) {B(x,1): x X} =V;
(ii) (s+1)|X|=nm;
(iii) s+1=p+2q, p>2q;
(iv) якщо 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}. Отже, ця система має єдиний розв'язок.. З іншого боку, система має очевидний розв'язок
x0=x1=…=xn-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) ми доведемо і обернене твердження.
Для того, щоб застосувати лему 3.2 покладемо s=3, p=3, q=1, V=G, ={0,1}, V(0)={(0,x): x }, V(1)={(1,x): x }. Зафіксуємо калейдоскопічне розфарбування : V {0,1,2,3} і позначимо Xi= -1(i), i {0,1,2,3}.За лемою 3.2, |Xi V(0)|= |Xi V(1)| для всіх i {0,1,2,3}. За лемою 3.1(іі), |Xi|= . Оскільки 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=
Loading...

 
 

Цікаве