Реферат на тему:
Розкладність графів. Хроматичні і калейдоскопічні числа
Нехай 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}.
Теорема 2. Якщо число ( (Gr) скінченне, то ( (Gr)( ( (Gr)+1.
Доведення. Спочатку припустимо, що граф Gr(V,E) скінченний і застосуємо
індукцію по числу його вершин. Для |V|=1 твердження очевидне. Розглянемо
довільний скінченний граф Gr(V,E), |V|>1 і зафіксуємо деяку його вершину
x. Видалимо з графа Gr(V,E) вершину x і всі ребра (x,y1),
(x,y2),…,(x,ym), що виходять з цієї вершини. Одержаний граф позначимо
Gr'(V’,E’). Оскільки ( (Gr’) ( ( (Gr) і |V’| 1+((vi+1), виберемо колір з
найменшим номером c, що не зустрічається серед кольорів вершин
{v1,v2,…,vi}, суміжних з вершиною vi+1, і покладемо ((vi+1)=c.
Підмножина A множини вершин графа Gr(V,E) називається незалежною, якщо
будь-які дві вершини x,y(A несуміжні. Число незалежності ((Gr)
скінченного графа Gr – це кількість елементів в найбільшій за розмірами
незалежній множині цього графа.
Теорема 4. Для будь-якого скінченного графа Gr(V,E), |V|=n справедливі
оцінки
n/((Gr) ( ((Gr)( n-((Gr) +1.
Доведення. Нехай ((Gr)=k. Тоді правильне k-розфарбування дає розбиття
множини V на k однокольорових класів V1,V2,…,Vk. Ясно, що кожен з цих
класів є незалежною підмножиною. Оскільки
n=|V1|+|V2|+…+|Vk|( k((Gr),
то ((Gr)( n/((Gr).
Для доведення верхньої оцінки виберемо незалежну підмножину S(V, що
містить ((Gr) елементів. Легко помітити, що ((Gr[V\S])( ((Gr)-1.
Оскільки |V\S|=n-((Gr), то ((Gr[V\S])(. n-((Gr). Звідси випливає, що
((Gr)(((Gr[V\S])+1( n-((Gr)+1.
Викладемо алгоритм Єршова-Кожухіна розфарбування скінченного графа, що
приводить до оцінки його хроматичного числа через кількість вершин і
ребер графа. В основі цього алгоритму лежить принцип склеювання вершин і
зведення початкового графу до графу з меншим числом вершин.
Надалі в цьому параграфі всі графи вважаються скінченними. Для вершини
v графа Gr(V,E) покладемо
S1(v)={x(V: d(v,x)=1}, S2(v)={y(V: d(v,y)=2}.
Склеювання вершин v1, v2 графа – це перетворення з двох кроків. На
першому кроці видаляються вершини v1, v2 разом з усіма інцидентними до
них ребрами. На другому кроці вибирається нова вершина v (V і
сполучається ребрами з усіма вершинами із V\{v1,v2}, з якими були
сполучені ребрами вершини v1, v2. В результаті склеювання число вершин
зменшується на одиницю, а число ребер не зростає.
Правильне розфарбування множини вершин графа Gr в ((Gr) кольорів
називається мінімальним розфарбуванням. Дві вершини графа називаються
спорідненими, якщо існує мінімальне розфарбування, при якому ці вершини
однокольорові.
Лема 1. Кожен граф Gr(V,E), відмінний від повного графа, має принаймні
одну пару споріднених вершин.
Доведення. Нехай |V|=n. Припустимо, що в деякому мінімальному
розфарбуванні графа взагалі немає двох однокольорових вершин. Тоді
((Gr)=n. Оскільки граф Gr неповний, то в ньому знайдеться пара v1, v2
несуміжних вершин. Склеїмо ці вершини і одержимо граф Gr’ з
|V(Gr’)|=n-1. Виберемо в ньому вершину v, в яку були склеєні вершини v1,
v2. Розклеїмо ці вершини і пофарбуємо їх в колір вершини v. Одержимо
правильне розфарбування графа 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
справедливі такі оцінки
;
.
Доведення. Спочатку доведено верхню оцінку (і). Якщо граф Gr неповний,
то за лемою 4 в ньому знайдеться пара споріднених вершин, відстань між
якими дорівнює 2. Склеїмо їх і за лемою 2 одержимо граф з тим самим
хроматичним числом. Зауважимо, що число вершин цього графа менше на
одиницю, а число ребер менше принаймні на одиницю. Повторюючи цю
процедуру s
Нашли опечатку? Выделите и нажмите CTRL+Enter
