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

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

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

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

 

ПОШУК:   

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

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

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

 

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

 

Нехай Gr(V,E) - граф, k - кардинал. Правильним k-розфарбуванням графа

Gr(V,E) називається розфарбування (: V(k, таке що будь-які дві суміжні

вершини різнокольорові. Хроматичним числом графа Gr називається

найменший кардинал k, для якого існує правильне k–розфарбування.

Хроматичне число графа Gr позначається ((Gr). Якщо ((Gr)=k, то граф Gr

називається k–хроматичним. Очевидно, що ((Gr)=1 тоді і тільки тоді, коли

E(Gr)=(.

 

Відмітимо, що ((Gr)=2 тоді і тільки тоді, коли множина вершин V(Gr) є

2-розкладною відносно множини E(Gr) усіх ребер графа.

 

Розглянемо хроматичні числа графів з точки зору корозкладності.

 

Нехай X – довільна непорожня множина, ( - деяка сім’я підмножин множини

X, k - кардинал. Множина X називається k–корозкладною відносно сім’ї (,

якщо існує розбиття X на k підмножин, таке що F(A для кожної підмножини

F(( і кожної підмножини A розбиття. В хроматичній термінології множина X

являється k–корозкладною відносно сім’ї (, якщо існує k-розфарбування X,

таке що жодна підмножина F(( не є однокольоровою. Припустимо, що сім’я (

не містить одноелементних підмножин і порожньої підмножини. Тоді X

являється |X|–корозкладною відносно сім’ї (. Найменший кардинал k, для

якого множина X являється k–корозкладною відносно сім’ї (, називається

показником корозкладності X відносно (.

 

Таким чином, хроматичне число графа Gr – це показник корозкладності

множини його вершин відносно сім’ї його ребер.

 

Послідовність x1,x2,…,xn, n(3 різних вершин графа Gr(V,E) називається

циклом, якщо

 

(x1,x2)(E, (x2,x3)(E,…,(xn-1,xn)(E, (x1,xn)(E.

 

Цикл називається парним (непарним), якщо число n парне (непарне).

 

Задача 1. Довести, що хроматичне число парного циклу дорівнює 2, а

непарного – 3.

 

Теорема 1. Хроматичне число графа Gr(V,E) дорівнює 2 тоді і тільки

тоді, коли E(( і граф не має непарних циклів.

 

Доведення. Необхідність випливає із задачі 1. При доведенні достатності

можна вважати, що граф Gr(V,E) зв'язний і |V|( 2. Зафіксуємо довільний

кістяк Tr(V,E') графа Gr(V,E), E'(E. Візьмемо довільну вершину x(V і

покладемо ((x)=0. Для кожної вершини y (V покладемо ((y)=0 (((y)=1) тоді

і тільки тоді, коли відстань від x до y в дереві Tr(V,E') парна

(непарна). Таким чином, визначено деяке розфарбування (: V({0,1}.

Візьмемо довільне ребро (y,z)(E. Якщо (y,z)(E', то ((y)(((z) за

означенням відображення (. Припустимо, що (y,z)(E'. Тоді знайдеться

вершина v(V, така що через вершини y,z,v проходить деякий цикл

 

v1,v2,…,vn,vn+1,…,vm

 

де v1=v, vn=y, vn+1=z, (vm,v)(E. Оскільки число m парне, то ((y)(((z).

 

Характеризація k-хроматичних графів для k(3 невідома. Більше того,

обчислення хроматичних чисел деяких природних класів графів може

виявитись досить тонкою проблемою. У цьому зв'язку пригадаємо знамениту

проблему чотирьох фарб. Ми обмежимося лише оцінками хроматичного числа

графа через простіші його інваріанти.

 

Позначимо через ( (x) локальний степінь вершини x графа Gr(V,E) і

покладемо ( (Gr)= sup {( (x): x(V}.

-----> Page:

0 [1] [2] [3] [4]

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