Задачи раскраски графов А.В.Пяткин. Вершинная раскраска Раскрасить вершины графа в минимальное число цветов так, чтобы смежные вершины получали бы разные. - презентация

1 Задачи раскраски графов А.В.Пяткин

2 Вершинная раскраска Раскрасить вершины графа в минимальное число цветов так, чтобы смежные вершины получали бы разные цвета (разбиение на независимые множества)

3 Хроматическое число Минимальное число цветов, необходимое для правильной раскарски вершин = 3 = 4 = 2

4 Нижние оценки для хроматического числа, где – мощность максимальной клики n/, где n – число вершин, а – мощность максимального независимого множества

5 Конструкция Мицельского Для любого k2 cуществуют графы с k и = 2. k = 2k = 3k = 4

6 Конструкция Мицельского Граф M k+1 строится из M k следующим образом: для каждой вершины v добавим ее копию v с тем же множеством соседей. Добавим вершину v 0, смежную с каждой вершиной v Покажем, что M k+1 нельзя раскрасить в k цветов

7 Конструкция Мицельского Предположим, что это не так. Можно считать, что вершина v 0 окрашена в цвет k Вершины графа M k, раскрашенные цветом k, перекрасим в цвета их копий из M k k k k MkMk MkMk k MkMk MkMk v0v0 v0v0

8 Верхние оценки для хроматического числа Граф называется t -вырожденным, если в любом его подграфе есть вершина степени не более t. Теорема. Если граф t -вырожденный, то t+1

9 Доказательство Индукция по n : при удалении любой вершины граф остается t -вырожденным Удалим вершину v степени t и раскрасим оставшийся граф в t+1 цвет по индукции Красим вершину v в цвет, отсутствующий среди цветов ее соседей Следствие. +1, где – максимальная степень графа

10 Оценка +1 достигается для нечетных циклов ( =2, =3 ) и полных графов ( =n–1, =n ). Теорема Брукса (1941). Если граф G не является полным графом или нечетным циклом, то (G).

11 Доказательство Для 2 утверждение очевидно. Пусть 3 Индукция по n. Удалим из G вершину v. Полученный граф H можно раскрасить в цветов (если H не является полным или нечетным циклом, то по индукции; иначе, степень графа H равна – 1 ).

12 Доказательство 1) В любой раскраске графа H все цвета 1,2,…, присутствуют среди цветов соседей вершины v. Обозначим через v i соседа v цвета i 2 1 N(v)N(v) v1v1 v v2v2 v

13 Доказательство 2) Пусть H i,j – подграф H, порожденный вершинами цветов i и j. Тогда v i и v j лежат в одной компоненте связности графа H i,j j i N(v)N(v) vjvj vivi i ij j i j Hi,jHi,j v

14 Доказательство В противном случае, можно перекрасить компоненту, cодержащую v i и окрасить вершину v цветом i j i N(v)N(v) vjvj vivi i ij j j j i Hi,jHi,j i j j N(v)N(v) vjvj vivi j ij i i i j Hi,jHi,j vv

15 Доказательство 3) Компонента связности графа H i,j, содержащая v i и v j, является путем P i,j j i N(v)N(v) vjvj vivi i ij j v Pi,jPi,j

16 Доказательство Если это не так, пусть u – ближайшая к v i вершина степени больше 2 в H i,j. Тогда ее можно перекрасить и разбить компоненту связности H i,j j i N(v)N(v) vjvj vivi i ij j v Hi,jHi,j j j i N(v)N(v) vjvj vivi ij j v Hi,jHi,j j uu

17 Доказательство 4) Для любых i,j,k пути P i,j и P j,k пересекаются только в вершине v j k j i N(v)N(v) vjvj vivi i i j j v Pi,jPi,j vkvk k k j j Pj,kPj,k

18 Доказательство Если пути P i,j и P j,k пересекаются в вершине uv j, то вершину u можно перекрасить и разбить компоненту связности k j i N(v)N(v) vjvj vivi i i j j v Pi,jPi,j vkvk k kj Pj,kPj,k k j i N(v)N(v) vjvj vivi i i j v Pi,jPi,j vkvk k kj Pj,kPj,k uu

19 Доказательство Так как G – не полный граф, то среди соседей вершины v найдутся две несмежные, скажем v 1 и v 2. Пусть u – сосед вершины v 1, окрашенный цветом 2. Перекрасим путь P 1, v2v2 v1v v P 1,2 v3v P 1,3 u v2v2 v1v v P 1,2 v3v P 1,3 u 1 3

20 Доказательство В полученной раскраске рассмотрим пути P 2,3 и P 1,2. Они пересекаются в вершине uv v2v2 v1v v P 1,2 v3v P 2,3 u

21 Реберная раскраска Раскраска ребер в минимальное число цветов, так чтобы не было смежных ребер одного цвета (разбиение на паросочетания) Ясно, что(G)= (L(G)) G L(G)L(G)

22 Очевидно,(G) Теорема Кёнига (1916). Если граф G двудольный, то(G)= Нижняя оценка

23 Доказательство Индукция по m Удалим ребро xy и раскрасим ребра оставшегося графа в цветов по индукции При каждой из вершин x и y останется по крайней мере по одному цвету, не использованному для раскраски примыкающих к ней ребер (свободные цвета).

24 Доказательство Пусть цвет a свободен при вершине x. Если он свободен и при вершине y, то красим ребро xy цветом a. Иначе, обозначим через b свободный цвет при вершине y. Рассмотрим цветочередующуюся (a,b)- цепь, начинающуюся в вершине y.

25 Доказательство Эта цепь не может закончиться в вершине x, поскольку граф не содержит нечетных циклов. После ее перекраски ребро xy красится цветом a y G x a a b b b y G x b a b b a a

26 Верхняя оценка Теорема Визинга (1964). Для любого графа G выполнена оценка(G) +1

27 Доказательство Индукция по m Для любого ребра xy, граф G\xy красится в +1 цвет. Тогда при каждой вершине есть свободный цвет. Более того: (*) Для любых цветов a и b, свободных при вершинах x и y соответственно, цветочередующаяся (a,b) -цепь, начинающаяся в вершине y, заканчивается в вершине x (иначе действуем как в Теореме Кёнига).

28 Доказательство Удалим ребро xy 0 и раскрасим полученный граф в +1 цвет. Выберем при x и y 0 свободные цвета a и a 0. При x есть ребро xy 1, окрашенное цветом a 0. Пусть a 1 – свободный при y 1 цвет. Тогда им окрашено некоторое ребро xy 2. И т.д. – строим максимальную последовательность y 0,y 1,…,y k, где ребро xy i окрашено в цвет a i, свободный при вершине y i-1

29 Доказательство Если при x нет ребра цвета a k, то перекрашиваем каждое ребро xy i в цвет a i y0y0 y1y1 a0a0 a1a1 y2y2 ykyk a2a2 akak y0y0 y1y1 a0a0 a1a1 y2y2 ykyk a2a2 akak x a x a akak akak

30 Доказательство Значит, найдется такое i, что a k =a i =b. Перекрасим каждое ребро xy t в цвет a t для t=0,1,…,k-1. Ребро xy k станет неокрашенным y0y0 yiyi a0a0 ai=bai=b y i+1 ykyk a i+1 y0y0 yiyi a0a0 b ykyk b y i+1 a i+1 x a x a ak=bak=b

31 Доказательство По (*), цветочередующаяся (a,b) -цепь, начинающаяся в вершине y k, заканчивается в вершине x. Более того, ее последним ребром будет ребро xy i x y0y0 yiyi a0a0 b ykyk b y i+1 a i+1 a

32 Доказательство Вернемся к исходной раскраске и перекрасим каждое ребро xy t в цвет a t для t=0,1,…,i-1. Ребро xy i станет неокрашенным. Но тогда цветочередующаяся (a,b) -цепь, начинающаяся в вершине y i, заканчивается в вершине y k, а не x. x y0y0 yiyi a0a0 b ykyk b y i+1 a i+1 a x y0y0 yiyi a0a0 b ykyk b y i+1 a i+1 a

33 Доказательство Значит, ее можно перекрасить и окрасить ребро xy i цветом a x y0y0 yiyi a0a0 b ykyk b y i+1 a i+1 a x y0y0 yiyi a0a0 b ykyk b y i+1 a i+1 a

34 Предписанная раскраска Каждая вершина (ребро) имеет свой собственный набор допустимых цветов Задача возникает при попытке продолжить имеющуюся частичную раскраску графа

35 Предписанное хроматическое число ch(G) Это минимальное k, при котором граф допускает правильную раскраску для любого предписания мощности не менее k при каждой вершине. Ясно, что ch(G) (G)

36 Пример граф G c ch(G)> (G) ? ?

37 Теорема. Для любого t3 существует двудольный граф G с ch(G)>t. Доказательство. G=K t,t t Предписания меньшей доли: непересекающися множества A 1,A 2,…,A t мощности t каждое Предписания большей доли: все варианты выбора по одному элементу из A 1,A 2,…,A t

38 Предписанная раскраска плоских графов Существует плоский граф G с ch(G)>4. Граф G a,b нельзя раскрасить в соответствии с предписанием b a Ga,bGa,b

39 ? b a Ga,bGa,b ? b Ga,bGa,b a

40 Предписанная раскраска плоских графов G 1,5 G 1,6 G 4,8 {1,2,3,4}{5,6,7,8} … Плоский граф G с ch(G)>4

41 Предписанная раскраска плоских графов Теорема Томассена (1994). Если G – плоский, то ch(G)5

42 Предписанная раскраска плоских графов Лемма. Пусть в плоском графе G внешняя грань ограничена циклом C=v 1 v 2 …v k, а все внутренние грани треугольные. Пусть v 1 и v 2 окрашены различными цветами a и b, остальные вершины цикла C имеют предписания мощности 3, а внутренние вершины – предписания мощности 5. Тогда существует раскраска графа G в соответствии с этим предписанием.

43 Доказательство Индукция по n. Рассмотрим 2 случая Случай 1. В цикле C есть хорда xy. Обозначим через С 1 ту часть цикла, которая содержит вершины v 1 и v 2 x C2C2 v1v1 v2v2 y C1C1

44 Доказательство x C2C2 v1v1 v2v2 y C1C1 x C2C2 v1v1 v2v2 y C1C1 Красим по индукции сначала C 1, а потом C 2.

45 Доказательство Случай 2. В цикле C нет хорд. Обозначим через u 1,u 2,…,u s соседей вершины v k, лежащих внутри цикла C u1u1 u2u2 v1v1 v2v2 C vkvk v k-1 usus

46 Доказательство В предписании вершины v k выберем цвета c и d, отличные от a и удалим их из предписаний вершин u 1,u 2,…,u s. Удалив вершину v k, получим меньший граф G с предписанием, удовлетворяющим условиям теоремы. u1u1 u2u2 v1v1 v2v2 C vkvk v k-1 usus a bcd G

47 Доказательство По индукции раскрасим граф G в соответствии с предписанием. Цвета c и d не использовались при раскраске вершин v 1,u 1,u 2,…,u s. Красим v k тем из них, который отличен от цвета вершины v k-1. u1u1 u2u2 v1v1 v2v2 C vkvk v k-1 usus a bcd G

48 Предписанная раскраска ребер Гипотеза Визинга. Для любого графа G, ch(G)= (G). Теорема Галвина (1995). Если граф G двудольный, то ch(G)= (G).

49 Лемма. Пусть в графе G задано вершинное предписание L. Предположим, ребра G можно ориентировать так, чтобы: (1) |L(v)|>d + (v) для каждой вершины v (2) В любом подграфе G найдется такое независимое множество A, что из каждой вершины v G\A в A ведет хотя бы одна дуга. Тогда вершины графа G можно раскрасить в соответствии с предписанием.

50 Доказательство леммы Индукция по n. Выберем цвет a и рассмотрим подграф G, порожденный вершинами, чьи предписания содержат a. Раскрасим вершины из A цветом a и удалим их из G. Удалим цвет a из предписаний остальных вершин графа G. Их предписания уменьшатся на 1. Но так как их исходящие полустепени также уменьшились хотя бы на 1, то оставшийся граф можно докрасить по индукции.

51 Доказательство теоремы Рассмотрим граф H=L(G). Построим для него ориентацию, удовлетворяющую условиям леммы. Пусть G=(X,Y; E). По теореме Кёнига (G)=. Обозначим через f(e) цвет ребра e в некоторой реберной раскраске графа G в цветов.

52 Доказательство теоремы Пусть e 1 и e 2 – два смежных в G ребра, причем f(e 1 )>f(e 2 ). Тогда если они смежны в X, то в H ориентируем дугу от e 1 к e 2, а если они смежны в Y, то в H ориентируем дугу от e 2 к e XY

53 Доказательство теоремы Ясно, что |d + (v)| 1, так как у дуги цвета k есть не более k 1 соседа в X, раскрашенных меньшими цветами и не более k соседей в Y раскрашенных большими цветами. 132 X Y

54 Доказательство теоремы Предположим, условие (2) леммы не выполнено. Рассмотрим минимальный по числу вершин подграф H, который ему не удовлетворяет. Пусть E=V(H). X Y E

55 Доказательство теоремы Пусть X – подмножество вершин из X, инцидентных дугам из E. Для каждой вершины x X выберем инцидентную ей дугу e x наименьшего цвета. Пусть U – множество вершин H, соответствующее всем таким дугам. X Y E X 132 U

56 Доказательство теоремы Ясно, что из любой другой вершины из H исходит дуга, ведущая в U. Если U независимо, то A=U. XY E X 132 U

57 Доказательство теоремы Пусть e и e смежны в U, причем f(e)

58 Доказательство теоремы Удалим e из H. По индукции, H\e содержит множество A, удовлетворяющее условиям леммы. Если e A, то A=A. Предположим, e A. X E X 132 A e e Y

59 Доказательство теоремы По определению A существует e A, в которую ведет дуга из e. По определению U e и e не могут быть смежны в X. Значит, они смежны в Y и f(e)

60 Доказательство теоремы Но тогда и e и e смежны в Y, причем f(e)

61 Упражнения 1. Доказать, что если G – это дополнение G, то max{ (G), (G)}n 1/2 2. Доказать, что (G) 1/2 + (2m+1/4) 1/2, где m – число ребер в G

62 Спасибо за внимание!