Задачи раскраски графов. Вершинная раскраска - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Задачи раскраски графов. Вершинная раскраска, слайд №1

Задачи раскраски графов. Вершинная раскраска, слайд №2

Задачи раскраски графов. Вершинная раскраска, слайд №3

Задачи раскраски графов. Вершинная раскраска, слайд №4

Задачи раскраски графов. Вершинная раскраска, слайд №5

Задачи раскраски графов. Вершинная раскраска, слайд №6

Задачи раскраски графов. Вершинная раскраска, слайд №7

Задачи раскраски графов. Вершинная раскраска, слайд №8

Задачи раскраски графов. Вершинная раскраска, слайд №9

Задачи раскраски графов. Вершинная раскраска, слайд №10

Задачи раскраски графов. Вершинная раскраска, слайд №11

Задачи раскраски графов. Вершинная раскраска, слайд №12

Задачи раскраски графов. Вершинная раскраска, слайд №13

Задачи раскраски графов. Вершинная раскраска, слайд №14

Задачи раскраски графов. Вершинная раскраска, слайд №15

Задачи раскраски графов. Вершинная раскраска, слайд №16

Задачи раскраски графов. Вершинная раскраска, слайд №17

Задачи раскраски графов. Вершинная раскраска, слайд №18

Задачи раскраски графов. Вершинная раскраска, слайд №19

Задачи раскраски графов. Вершинная раскраска, слайд №20

Задачи раскраски графов. Вершинная раскраска, слайд №21

Задачи раскраски графов. Вершинная раскраска, слайд №22

Задачи раскраски графов. Вершинная раскраска, слайд №23

Задачи раскраски графов. Вершинная раскраска, слайд №24

Задачи раскраски графов. Вершинная раскраска, слайд №25

Задачи раскраски графов. Вершинная раскраска, слайд №26

Задачи раскраски графов. Вершинная раскраска, слайд №27

Задачи раскраски графов. Вершинная раскраска, слайд №28

Задачи раскраски графов. Вершинная раскраска, слайд №29

Задачи раскраски графов. Вершинная раскраска, слайд №30

Задачи раскраски графов. Вершинная раскраска, слайд №31

Задачи раскраски графов. Вершинная раскраска, слайд №32

Задачи раскраски графов. Вершинная раскраска, слайд №33

Задачи раскраски графов. Вершинная раскраска, слайд №34

Задачи раскраски графов. Вершинная раскраска, слайд №35

Задачи раскраски графов. Вершинная раскраска, слайд №36

Задачи раскраски графов. Вершинная раскраска, слайд №37

Задачи раскраски графов. Вершинная раскраска, слайд №38

Задачи раскраски графов. Вершинная раскраска, слайд №39

Задачи раскраски графов. Вершинная раскраска, слайд №40

Задачи раскраски графов. Вершинная раскраска, слайд №41

Задачи раскраски графов. Вершинная раскраска, слайд №42

Задачи раскраски графов. Вершинная раскраска, слайд №43

Задачи раскраски графов. Вершинная раскраска, слайд №44

Задачи раскраски графов. Вершинная раскраска, слайд №45

Задачи раскраски графов. Вершинная раскраска, слайд №46

Задачи раскраски графов. Вершинная раскраска, слайд №47

Задачи раскраски графов. Вершинная раскраска, слайд №48

Задачи раскраски графов. Вершинная раскраска, слайд №49

Задачи раскраски графов. Вершинная раскраска, слайд №50

Задачи раскраски графов. Вершинная раскраска, слайд №51

Задачи раскраски графов. Вершинная раскраска, слайд №52

Задачи раскраски графов. Вершинная раскраска, слайд №53

Задачи раскраски графов. Вершинная раскраска, слайд №54

Задачи раскраски графов. Вершинная раскраска, слайд №55

Задачи раскраски графов. Вершинная раскраска, слайд №56

Задачи раскраски графов. Вершинная раскраска, слайд №57

Задачи раскраски графов. Вершинная раскраска, слайд №58

Задачи раскраски графов. Вершинная раскраска, слайд №59

Задачи раскраски графов. Вершинная раскраска, слайд №60

Задачи раскраски графов. Вершинная раскраска, слайд №61

Задачи раскраски графов. Вершинная раскраска, слайд №62

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задачи раскраски графов. Вершинная раскраска. Доклад-сообщение содержит 62 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

Оценка  ≤ +1 достигается для нечетных циклов (=2, =3) и полных графов (=n–1, =n). Оценка  ≤ +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. Обозначим через vi соседа v цвета i

Слайд 13

Описание слайда:

Доказательство 2) Пусть Hi,j – подграф H, порожденный вершинами цветов i и j. Тогда vi и vj лежат в одной компоненте связности графа Hi,j

Слайд 14

Описание слайда:

Доказательство В противном случае, можно перекрасить компоненту, cодержащую vi и окрасить вершину v цветом i

Слайд 15

Описание слайда:

Доказательство 3) Компонента связности графа Hi,j, содержащая vi и vj, является путем Pi,j

Слайд 16

Описание слайда:

Доказательство Если это не так, пусть u – ближайшая к vi вершина степени больше 2 в Hi,j. Тогда ее можно перекрасить и разбить компоненту связности Hi,j

Слайд 17

Описание слайда:

Доказательство 4) Для любых i,j,k пути Pi,j и Pj,k пересекаются только в вершине vj

Слайд 18

Описание слайда:

Доказательство Если пути Pi,j и Pj,k пересекаются в вершине u≠vj, то вершину u можно перекрасить и разбить компоненту связности

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

Доказательство В полученной раскраске рассмотрим пути P2,3 и P1,2. Они пересекаются в вершине u≠v2

Слайд 21

Описание слайда:

Реберная раскраска Раскраска ребер в минимальное число цветов ’ , так чтобы не было смежных ребер одного цвета (разбиение на паросочетания) Ясно, что ’(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

Слайд 26

Описание слайда:

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

Слайд 27

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

Описание слайда:

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

Слайд 28

Описание слайда:

Доказательство Удалим ребро xy0 и раскрасим полученный граф в +1 цвет. Выберем при x и y0 свободные цвета a и a0. При x есть ребро xy1, окрашенное цветом a0. Пусть a1 – свободный при y1 цвет. Тогда им окрашено некоторое ребро xy2. И т.д. – строим максимальную последовательность y0,y1,…,yk, где ребро xyi окрашено в цвет ai, свободный при вершине yi-1

Слайд 29

Описание слайда:

Доказательство Если при x нет ребра цвета ak, то перекрашиваем каждое ребро xyi в цвет ai

Слайд 30

Описание слайда:

Доказательство Значит, найдется такое i, что ak=ai=b. Перекрасим каждое ребро xyt в цвет at для t=0,1,…,k-1. Ребро xyk станет неокрашенным

Слайд 31

Описание слайда:

Доказательство По (*), цветочередующаяся (a,b)-цепь, начинающаяся в вершине yk, заканчивается в вершине x. Более того, ее последним ребром будет ребро xyi

Слайд 32

Описание слайда:

Доказательство Вернемся к исходной раскраске и перекрасим каждое ребро xyt в цвет at для t=0,1,…,i-1. Ребро xyi станет неокрашенным. Но тогда цветочередующаяся (a,b)-цепь, начинающаяся в вершине yi, заканчивается в вершине yk, а не x.

Слайд 33

Описание слайда:

Доказательство Значит, ее можно перекрасить и окрасить ребро xyi цветом a

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

Теорема. Для любого t≥3 существует двудольный граф G с ch(G)>t. Теорема. Для любого t≥3 существует двудольный граф G с ch(G)>t. Доказательство. G=Kt,tt Предписания меньшей доли: непересекающися множества A1,A2,…,At мощности t каждое Предписания большей доли: все варианты выбора по одному элементу из A1,A2,…,At

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

Слайд 40

Описание слайда:

Предписанная раскраска плоских графов Плоский граф G с ch(G)>4

Слайд 41

Описание слайда:

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

Слайд 42

Описание слайда:

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

Слайд 43

Описание слайда:

Доказательство Индукция по n. Рассмотрим 2 случая Случай 1. В цикле C есть хорда xy. Обозначим через С1 ту часть цикла, которая содержит вершины v1 и v2

Слайд 44

Описание слайда:

Доказательство Красим по индукции сначала C1, а потом C2.

Слайд 45

Описание слайда:

Доказательство Случай 2. В цикле C нет хорд. Обозначим через u1,u2,…,us соседей вершины vk, лежащих внутри цикла C

Слайд 46

Описание слайда:

Доказательство В предписании вершины vk выберем цвета c и d, отличные от a и удалим их из предписаний вершин u1,u2,…,us. Удалив вершину vk, получим меньший граф G’ с предписанием, удовлетворяющим условиям теоремы.

Слайд 47

Описание слайда:

Доказательство По индукции раскрасим граф G’ в соответствии с предписанием. Цвета c и d не использовались при раскраске вершин v1,u1,u2,…,us. Красим vk тем из них, который отличен от цвета вершины vk-1.

Слайд 48

Описание слайда:

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

Слайд 49

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

Описание слайда:

Лемма. Пусть в графе G задано вершинное предписание L. Предположим, ребра G можно ориентировать так, чтобы: Лемма. Пусть в графе 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

Описание слайда:

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

Слайд 53

Описание слайда:

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

Слайд 54

Описание слайда:

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

Слайд 55

Описание слайда:

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

Слайд 56

Описание слайда:

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

Слайд 57

Описание слайда:

Доказательство теоремы Пусть e и e’ смежны в U, причем f(e)<f(e’). Так как e и e’ смежны в Y, то дуга в H направлена от e к e’.

Слайд 58

$Доказательство теоремы Удалим e из H’. По индукции, H’\e содержит множество A’, удовлетворяющее условиям леммы. Если e’A’, то A=A’. Предположим, e’A’.$

Описание слайда:

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

Слайд 59

Описание слайда:

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

Слайд 60

Описание слайда:

Доказательство теоремы Но тогда и e и e’’ смежны в Y, причем f(e)<f(e’’). Значит в H есть дуга из e в e’’, т.е. A=A’ удовлетворяет условиям леммы для подграфа H’.