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

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

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

Нехай 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<((Gr)+1, то знайдемо число

i({1,2,…,((Gr)+1}\{((y1),((y2),…,((ym)}

і покладемо ((x)=i.

Для поширення твердження теореми на нескінченні графи можна скористатися принципом компактності [20, p. 13].

Задача 2. Довести, що ( (Gr)( ( (Gr), якщо ( (Gr) - нескінченний кардинал.

Теорема 2. дає досить точну оцінку хроматичного числа за умови, що локальні степені вершин приблизно однакові. Якщо ж граф має вершини, локальні степені вершин якого різко відрізняються, то ця оцінка значно завищена. Наприклад це так для зірки, хроматичне число якої ( 2. В подібних ситуаціях значно кращу оцінку дає наступна теорема.

Теорема 3. Нехай Gr(V,E) - скінченний граф, V={v1,v2,…,vn}, ((v1)(((v2)(…(((vn).Тоді



Доведення. Покладемо ((v1)=1. Припустимо, що вершини v1, v2,…, vi вже пофарбовано в кольори {1,2,…,n(i)}, n(i)( i. Якщо i+1 ( 1+((vi+1), покладемо ((vi+1)=n(i)+1. Якщо i+1 > 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.