Головна Головна -> Реферати українською -> Математика -> Розкладність графів. Калейдоскопічні графи

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

Назва:
Розкладність графів. Калейдоскопічні графи
Тип:
Реферат
Мова:
Українська
Розмiр:
27,53 KB
Завантажень:
47
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3 
Однорідний граф Gr(V,E) скінченного степеня s називається калейдоскопічним, якщо існує розфарбування : V{0,1,,s}, таке що |(B(x,1))|=s+1 для будь-якого xV. В цьому разі розфарбування теж називається калейдоскопічним. Отже, калейдоскопічні графи – це графи, що допускають калейдоскопічне розфарбування. Дамо рівносильне означення: розфарбування : 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' куба, симетричну до деякої вершини yB(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): xX} =V;

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

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

(iv) якщо xV(i), i{0,1}, то |B(x,1)V(i)|=p, |B(x,1)(V\V(i)|=q.

Тоді |XV(0)|=|XV(1)|.

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

Додамо ці нерівності і отримаємо 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): xX} =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, S={a,b,b-1,e}.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок