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

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

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

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

Gr в n-1 кольорів, що суперечить припущенню (Gr)=n.
Лема 2. Якщо граф Gr' отримано з графа Gr склеюванням пари споріднених вершин, то (Gr')= (Gr).
Доведення. Нерівність (Gr') (Gr) очевидна. Нерівність (Gr) (Gr') вірна, якщо склеюється довільна пара несуміжних вершин.
Лема 3 Для будь-якого графа Gr з хроматичним числом k існує послідовність попарних склеювань вершин, що приводить до повного графу з k вершинами.
Доведення. В графі Gr знаходимо пару споріднених вершин і склеюємо їх. За лемою 2 хроматичне число при цьому не змінюється. За лемою 6.1 такі склеювання можна робити доти, поки не отримаємо повний граф.
Лема 4. Якщо v - вершина графа Gr(V,E) і множина S2(v) непорожня,то знайдеться вершина u S2(v) , споріднена з вершиною v.
Доведення. Зафіксуємо деяке мінімальне розфарбування графа Gr. Нехай при цьому вершина v пофарбована кольором . Якщо деяка вершина з S2(v) теж кольору , лему доведено. Припустимо, що в множині S2(v) немає вершин кольору . Візьмемо довільну вершину u S2(v), пофарбовану кольором , . Розглянемо два випадки.
Якщо в S1(v) немає вершин кольору , то перефарбуємо вершину v кольором .
Припустимо, що множина R усіх вершин із S1(v) кольору непорожня. Перефарбуємо ці вершини кольором , а вершину v - кольором .
Алгоритм Єршова-Кожухіна складається з двох етапів - згортки і розгортки. Спираючись на лему 4 вибираємо пари вершин, відстань між якими дорівнює 2, і склеїмо їх. Згідно з лемою 3 згортка закінчується побудовою повного графа. Розфарбуємо його вершини різними кольорами і розгорткою отримаємо правильне розфарбування початкового графа. При вдалому виборі послідовності склеюваних вершин це розфарбування мінімальне. В загальному випадку одержимо правильне розфарбування, наближене до мінімального.
Застосуємо алгоритм Єршова-Кожухіна для оцінки хроматичного числа. Позначимо через [x] і {x} цілу та дробові частини числа x.
Теорема 5. Для довільного зв'язного графа Gr(V,E), |V|=n, |E|=m справедливі такі оцінки
(i) (Gr) ;
(ii) (Gr) .
Доведення. Спочатку доведено верхню оцінку (і). Якщо граф Gr неповний, то за лемою 4 в ньому знайдеться пара споріднених вершин, відстань між якими дорівнює 2. Склеїмо їх і за лемою 2 одержимо граф з тим самим хроматичним числом. Зауважимо, що число вершин цього графа менше на одиницю, а число ребер менше принаймні на одиницю. Повторюючи цю процедуру s|V(Grs )|= (Grs )= (Gr)=n-s
Позначимо через Gr0 , Gr1,…,Grs , Gr0=Gr послідовність графів, що з'явилися в результаті попарних склеювань. Повний граф Grs має (Gr)( (Gr)-1)/2 ребер. Це число на m- (Gr)( (Gr)-1)/2 менше, ніж число ребер графа Gr. Оскільки на кожному кроці граф Gri має принаймні на одне ребро менше, ніж граф Gri-1, то
m- (Gr)( (Gr)-1)/2 s.
Таким чином, маємо нерівність
m- (Gr)( (Gr)-1)/2 n- (Gr).
Розв'яжемо цю нерівність відносно (Gr) і одержимо
(Gr) (3+ /2.
Доведемо нижню оцінку (іі). Позначимо (Gr)=k. Назвемо відсутнім ребром (vq,vp) в графі Gr будь-яку упорядковану пару несуміжних вершин, а також усі пари (vq,vq). Очевидно, що кількість відсутніх ребер дорівнює n2 -2m. Зафіксуємо деяке мінімальне розфарбування графа Gr. Нехай Xi - множина усіх вершин кольору i, ni=|Xi|, i {1,2,…,k}. Оскільки усі вершини множини Xi попарно несуміжні, то загальне число відсутніх ребер, утворених лише вершинами з Xi , дорівнює ni2. Звідси випливає нерівність
n2 -2m
(1)
за додаткової умови
= n.
(2)
Знайдемо мінімум p функції F= за умови (2) на множині цілих чисел. Для цього покладемо
ni = [n/k]+yi, l=n-[n/k]k,
(3)
де n/k - значення ni, що мінімізує функцію F за умови (2) на множині раціональних чисел. Очевидно, що
= l, 0 l k.
(4)
Можна показати, що знаходження мінімуму функції F за умови (2) зводиться до знаходження мінімуму функції за умови (4). Цей мінімум досягається, наприклад, при
y1=y2=…=yk-l=0, yk-l+1=…=yk=1.
Звідси випливає, що
p=n2/k+k(n/k-[n/k])(1+[n/k]-n/k),
(5)
де n2/k - мінімум функції F на множині раціональних чисел. Отже, нерівність (1) можна переписати у такому вигляді
k2(n/k-[n/k])(1+[n/k]-n/k) (n2-2m)k-n2
(6)
З цієї нерівності випливає, що
(Gr) [ x0],
(7)
де x0 - корінь рівняння
x2(n/x-[n/x])(1+[n/x]-n/x) (n2-2m)x-n2
(8)
що лежить на відрізку від 1 до n.
Досліджуючи поведінку лівої та правої частин рівняння (8), можна показати, що [n/x0]=[n/x1], де x1 - корінь рівняння
(n2-2m)x-n2=0.
Обчислимо [n/x1] і поставимо його в (8). Одержимо лінійне рівняння відносно x, з якого знаходимо
x0 = .
Враховуючи (7), одержуємо оцінку (іі).
Наступний приклад показує, що верхня оцінка (і) в теоремі 6.5 є точною.
Приклад 1. Побудуємо зв'язний граф Gr з n вершинами і m ребрами, для якого (Gr)= , де
=[(3+ ) 2].
(9)
Очевидно, що число m ребер зв'язного графа з n вершинами задовольняє нерівності
n-1 m n(n-1)/2.
Враховуючи (9) одержуємо нерівності
n, ( -1) /2 m, n- m- ( -1) /2 .
Граф Gr будуємо так: виберемо довільну вершину повного графа з вершинами і приєднаємо до неї ланцюг з n- вершинами і n- ребрами, а решту
m- ( -1) /2 -(n- )
ребер визначаємо довільним чином. Оскільки граф Gr містить повний граф з вершинами, то (Gr) . З нерівності (і) випливає, що (Gr) . Отже, (Gr)= .
Розглянемо довільний граф Gr(V,E). Калейдоскопічним число графа Gr(V,E) називається найменший кардинал k(Gr), для якого існує розфарбування : V k(Gr), таке що в кожній кулі B(x,1), x V немає двох однокольорових вершин. Зрозуміло, що (Gr)+1 k(Gr) . |V|. Побудуємо допоміжний граф Gr'(V,E'), де E' - множина усіх пар різних вершин із V, відстань між якими в графі Gr(V,E) не перевищує 2.
Задача 3. Довести, що k(Gr)= (Gr').
Задача 4. Довести, що k(Gr) (Gr)( (Gr)-1)+1.
Задача 5. Нехай Grn - цикл з n вершинами, n 3. Довести, що
k(Grn)=
Задача 6. Довести, що k (Tr)= (Tr)+1 для кожного дерева Tr.
Задача 7. Довести, що однорідний граф Gr скінченного степеня k калейдоскопічний тоді і тільки тоді, коли k (Gr)=k+1.
Loading...

 
 

Цікаве