UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваРозкладність графів. Калейдоскопічні графи (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2093
Скачало330
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Однорідний граф 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 задовольняють систему

-----> Page:

0 [1] [2] [3] [4] [5] [6]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ