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

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

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

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


Реферат на тему:
Розкладність графів. Хроматичні і калейдоскопічні числа
Нехай 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'|<|V|, то за припущенням індукції існує відображення : V' {1,2,…, (Gr)+1}, таке що (y) (z) для кожного ребра (y,z) E'. Оскільки m 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[VS]) (Gr)-1. Оскільки |VS|=n- (Gr), то (Gr[VS]) . n- (Gr). Звідси випливає, що
(Gr) (Gr[VS])+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. Одержимо правильне розфарбування графа
Loading...

 
 

Цікаве