Правильная раскраска графа; потоки в сетях

Дисциплина «Алгоритмы и структуры данных» Лекция № 13 Правильная раскраска графа. Потоки в сетях. Теорема Форда-Фолкерсона. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Правильная раскраска графа. Определения. Пусть G=(V, E) – обыкновенный граф, k – натуральное число. Функция f: V{1,…,k} называется раскраской графа. Раскраска называется правильной, если для любых смежных вершин x, y  V справедливо неравенство f(x)  f(y). Число k – число красок раскраски f. Правильность раскраски означает, что смежные вершины раскрашиваются в разные цвета. Определения. Пусть G=(V, E) – обыкновенный граф, k – натуральное число. Функция f: V{1,…,k} называется раскраской графа. Раскраска называется правильной, если для любых смежных вершин x, y  V справедливо неравенство f(x)  f(y). Число k – число красок раскраски f. Правильность раскраски означает, что смежные вершины раскрашиваются в разные цвета. Определения. Наименьшее число красок, правильной раскраски графа необходимое G для называется хроматическим числом графа G. Хроматическое число обозначается через c(G). Правильную раскраску таким числом красок будем называть оптимальной. Определения. Наименьшее число красок, правильной раскраски графа необходимое G для называется хроматическим числом графа G. Хроматическое число обозначается через c(G). Правильную раскраску таким числом красок будем называть оптимальной. c(G1)= ? c(G2)= ? Алгоритм раскраски графа Алгоритм состоит в следующем. 1. Упорядочиваем вершины графа G: V={v1,v2,…,vn}. 2. Вершину v1 красим первой краской. 3. Предположим, что вершины v1,…,vi уже раскрашены и на это использовано m красок. Если на раскрашенные вершины, смежные с vi+1, использованы все краски, то vi+1 раскрашиваем m+1 краской. Если среди m красок найдется краска, которая не использована для вершин, смежных с vi+1, то вершину vi+1 красим этой краской. Приведенный алгоритм последовательной раскраски. часто Нетрудно привести примеры, не является оптимальной. называют когда такая алгоритмом раскраска Определения. Наименьшее число красок, правильной раскраски графа необходимое G для называется хроматическим числом графа G. Хроматическое число обозначается через c(G). Правильную раскраску таким числом красок будем называть оптимальной. c(G1)= ? c(G2)= ? Оценка значения хроматического числа нижние оценки для c(G). Определение. Плотностью j(G) графа G наибольшее число вершин полного подграфа графа G. Следующее утверждение очевидно. называется Предложение 1. Для любого графа G выполняется неравенство j(G) ≤ c(G). Оценка значения хроматического числа нижние оценки для c(G). Определение. Множество попарно несмежных вершин графа называется независимым множеством. Числом независимости b(G) графа G называется наибольшее число вершин независимого множества. b(G1)=3, b(G2)=2. Предложение 2. Для любого графа G выполняется неравенство n/b(G)c(G Оценка значения хроматического числа нижние оценки для c(G). Нижние оценки хроматического числа в предложениях 1 и 2 обладают еще одним недостатком: задача вычисления чисел j(G) и b(G) столь же сложна, как и задача вычисления хроматического числа. (подробно о сложности задач см. в книге Гэри и Джонсона .) Оценка значения хроматического числа нижние полиномиальные оценки для c(G). Предложение 3. Для любого графа G выполняется неравенство • • n2/(n2 – 2m)  c(G). Отметим, что для полного графа 2m=n(n-1), поэтому для произвольного графа n2–2m>0. (По поводу доказательства предложения 3 см. книгу Н. Кристофидеса, стр.78.) Оценка значения хроматического числа Верхняя оценка для c(G). Из верхних оценок укажем одну, приведенную в теореме 5.3, которую часто называют теоремой Брукса. (Теорема доказана Бруксом в 1941г.) Через D(G) обозначим наибольшую степень вершин графа G. • Теорема. Пусть G=(V,E) – связный неполный граф и D(G)3. Тогда c(G)D(G). Определения. Наименьшее число красок, правильной раскраски графа необходимое G для называется хроматическим числом графа G. Хроматическое число обозначается через c(G). Правильную раскраску таким числом красок будем называть оптимальной. c(G1)= ? c(G2)= ? Определения. Наименьшее число красок, правильной раскраски графа необходимое G для называется хроматическим числом графа G. Хроматическое число обозначается через c(G). Правильную раскраску таким числом красок будем называть оптимальной. c(G1)= 3 c(G2)= 4 Оценка значения хроматического числа нижние оценки для c(G). Определение. Множество попарно несмежных вершин графа называется независимым множеством. Числом независимости b(G) графа G называется наибольшее число вершин независимого множества. b(G1)=?, b(G2)=? Примеры задач, в которых используется правильная раскраска. Область применения: Разбиение множества вершин графа на классы попарно несмежных между вершин. Довольно часто дополнительно требуется, чтобы таких классов было наименьшее число. Примеры задач, сводимые к нахождению хроматического числа: • Задача составления расписаний; • Задача распределения ресурсов; • Задача экономии памяти. Потоки в сетях. Теорема Форда-Фолкерсона. Дисциплина «Технологии и методы программирования» Лекция № 11 Потоки в сетях. Теорема Форда-Фолкерсона. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Определения: понятие сети Определение. Сетью N называется пара , где G – ориентированный граф, α - функция из множества вершин графа в множество неотрицательных действительных чисел. N = (G, α) Если е – дуга графа G, то число α(е) в зависимости от контекста называется либо длиной, либо весом, либо пропускной способностью дуги. Определения: источник и сток. Вершину v сети N, для которой r–(v)>0 и r+(v)=0 будем называть источником, а вершину w, для которой r+(w)>0 и r–(w)=0 – стоком. Предполагается, что N=(G, a) – сеть, имеющая один источник a и один сток b: Определения: источник и сток. Вершину v сети N, для которой r–(v)>0 и r+(v)=0 будем называть источником, а вершину w, для которой r+(w)>0 и r–(w)=0 – стоком. Предполагается, что N=(G, a) – сеть, имеющая один источник a и один сток b. Если это не так… Определения: источник и сток. Вершину v сети N, для которой r–(v)>0 и r+(v)=0 будем называть источником, а вершину w, для которой r+(w)>0 и r–(w)=0 – стоком. Предполагается, что N=(G, a) – сеть, имеющая один источник a и один сток b. Если это не так, то конструируется новый виртуальный узел с инцидентными дугами, пропускные способности которых равны полуисходам исходных источников: 2 3 3 Определения: источник и сток. Вершину v сети N, для которой r–(v)>0 и r+(v)=0 будем называть источником, а вершину w, для которой r+(w)>0 и r–(w)=0 – стоком. Пусть N=(G,a) – сеть, имеющая один источник a и один сток b. Предположим, что сеть N представляет собой схему линий связи, где вершинам соответствуют узлы связи, дугам – линии связи с указанным направлением передачи информации. Если е – дуга сети N, то величина a(е) означает ограничение количества информации, передаваемой по дуге е за некоторый промежуток времени. Возникает следующий вопрос. Какое наибольшее количество информации можно передать из а в b и как это сделать? Пропускная способность и поток в сети Величина a(е) называется пропускной способностью дуги е. Определение. Пусть N=(G, a) – сеть, а – источник и b – сток этой сети. Потоком через сеть N называется функция j: ЕR+ {0}, удовлетворяющая двум условиям: 1) j(е)  a(е) для любой дуги е  Е, 2) в сети (G,j) у любой вершины, кроме источника и стока, полустепень исхода равна полустепени захода. Число j(е) называется значением потока через дугу е. Полустепенью исхода r–(v) вершины v назовем сумму j(е) по всем дугам, исходящим из v, Полустепенью захода r+(v) вершины v – сумму j(е) по всем дугам, заходящим в v. Задача нахождения максимального потока в сети. Лемма. Пусть j - поток через сеть N=(G, a). Тогда сумма потоков через дуги, инцидентные источнику, равна сумме потоков через дуги, инцидентные стоку. Такая сумма называется величиной потока. Поток называется максимальным, если он имеет наибольшую величину (среди всех потоков через данную сеть). Задача нахождения максимального потока в сети. Лемма. Пусть j - поток через сеть N=(G, a). Тогда сумма потоков через дуги, инцидентные источнику, равна сумме потоков через дуги, инцидентные стоку. Такая сумма называется величиной потока. Поток называется максимальным, если он имеет наибольшую величину (среди всех потоков через данную сеть). Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. сумма пропускных способностей входящих в него дуг. Примерами разрезов для данной сети будут множества: S1={(a,y), (a,x), (a,z)}, S2={(a,z), (x,z), (y,z), (y,b)}, S3={(y,b), z,b)}, … Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. Определение. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Примерами разрезов для данной сети будут множества: S1={(a,y), (a,x), (a,z)}, S2={(a,z), (x,z), (y,z), (y,b)}, S3={(y,b), z,b)}, … Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. Определение. Пропускной способностью a(S) разреза S называется сумма пропускных способностей входящих в него дуг. Пропускные способности разрезов равны: S1={(a,y), (a,x), (a,z)}, a(S1)=… S2={(a,z), (x,z), (y,z), (y,b)}, a(S2)=… S3={(y,b), z,b)} a(S3)=… Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. Определение. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Пропускные способности разрезов a(S): S1={(a,y), (a,x), (a,z)}, a(S1)=7 S2={(a,z), (x,z), (y,z), (y,b)}, a(S2)=6 S3={(y,b), z,b)} a(S3)=6 Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. Определение. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Пропускные способности разрезов a(S): S1={(a,y), (a,x), (a,z)}, a(S1)=7 S2={(a,z), (x,z), (y,z), (y,b)}, a(S2)=6 S3={(y,b), z,b)} a(S3)=6 Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. Определение. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Пропускные способности разрезов a(S): S1={(a,y), (a,x), (a,z)}, a(S1)=7 S2={(a,z), (x,z), (y,z), (y,b)}, a(S2)=6 S3={(y,b), z,b)}, a(S3)=6 Разрез называется минимальным, если он имеет наименьшую пропускную способность (среди всех разрезов данной сети). Разрезы сети. Определение. Разрезом сети N, имеющей один источник и один сток, называется множество дуг S такое, что любая цепь от источника до стока содержит дугу из S. Определение. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Пропускные способности разрезов a(S): S1={(a,y), (a,x), (a,z)}, a(S1)=7 S2={(a,z), (x,z), (y,z), (y,b)}, a(S2)=6 S3={(y,b), z,b)}, a(S3)=6 Разрез называется минимальным, если он имеет наименьшую пропускную способность (среди всех разрезов данной сети). !! Минимальных разрезов может быть несколько. Теорема Форда - Фолкерсона Лемма. Величина любого потока через сеть не превосходит пропускной способности любого разреза этой сети. Теорема Форда-Фолкерсона. В любой сети величина максимального потока равна пропускной способности минимального разреза. Поскольку на чертеже разрез сети построить проще, чем найти поток через сеть, то теорему Форда-Фолкерсона в случае простых сетей можно использовать для нахождения максимальных потоков в сети. Однако для более-менее сложной сети, даже если найдена величина максимального потока, сам поток построить трудно. Алгоритм нахождения максимального потока Дана сеть N=(G,a), a – источник, b – сток сети, a:EN. Шаг 1. Если не существует пути из источника в сток, то положить j=0 и перейти к шагу 4, иначе выбрать непустое множество T непересекающихся по дугам путей из a в b. Если e1,e2,…,ek – путь из T, т.е. последовательность дуг, то положить j(e1)= j(e2)=…= j(ek)=min{a(e1),…,a(ek)}. Для дуг e, через которые не проходят пути из T, положить j(e)=0. В результате получаем ненулевой поток j через сеть (G,a). Шаг 2. Исходя из сети (G,a) и потока j построить сеть (G′,a′) следующим образом. Граф G’ будет иметь те же вершины, что и граф G. Если e – дуга графа G и a(e) - j(e)0, то e – дуга графа G′ и a′(e)=a(e) - j(e). Если e – дуга графа G и j(e)0, то вводим дугу обратной ориентации, нежели e, и полагаем a′( ) = j(e). В случае, когда возникают кратные дуги e1 и e2, то вводим вместо них одну дугу e и полагаем a′(e)=a′(e1) + a′(e2). Шаг 3. Если в сети (G′,a′) не существует пути из a в b, то перейти к шагу 4, иначе в сети (G’,a’) построить ненулевой поток j’ так, как это предписано шагом 1. Для сети (G,a) положить j=j+j’ и перейти к шагу 2. Шаг 4. Выдать j. Конец работы алгоритма. Алгоритм нахождения максимального потока Дана сеть N=(G,a), a – источник, b – сток сети, a:EN. Шаг 1. Если не существует пути из источника в сток, то положить j=0 и перейти к шагу 4, иначе выбрать непустое множество T непересекающихся по дугам путей из a в b. Если e1,e2,…,ek – путь из T, т.е. последовательность дуг, то положить j(e1)= j(e2)=…= j(ek)=min{a(e1),…,a(ek)}. Для дуг e, через которые не проходят пути из T, положить j(e)=0. В результате получаем ненулевой поток j через сеть (G,a). В качестве множества T на первом шаге алгоритма выбрано множество из двух путей: a,v1,v4,b и a,v2,v5,b. Алгоритм нахождения максимального потока Шаг 2. Исходя из сети (G,a) и потока j построить сеть (G′,a′) следующим образом. Граф G’ будет иметь те же вершины, что и граф G. Если e – дуга графа G и a(e) - j(e)0, то e – дуга графа G′ и a′(e)=a(e) - j(e). Если e – дуга графа G и j(e)0, то вводим дугу обратной ориентации, нежели e, и полагаем a′( ) = j(e). В случае, когда возникают кратные дуги e1 и e2, то вводим вместо них одну дугу e и полагаем a′(e)=a′(e1) + a′(e2). На рисунке представлена сеть (G′,a′), полученная после выполнения шага 2, с указанным (в скобках) потоком j′. В качестве множества T для построения потока j′ взято множество, состоящее из одного пути: a,v3,v5,v2,v6,b. Алгоритм нахождения максимального потока Шаг 3. Если в сети (G′,a′) не существует пути из a в b, то перейти к шагу 4, иначе в сети (G’,a’) построить ненулевой поток j’ так, как это предписано шагом 1. Для сети (G,a) положить j=j+j’ и перейти к шагу 2. . На рисунке изображен поток j+j′ для сети (G, a) после 3 шага. Этим завершен один проход алгоритма. Обратим внимание на то, что для e=(v2,v5) (j+j′)(e)=j(e)–j′( )=1. Алгоритм нахождения максимального потока Второй проход алгоритма Алгоритм нахождения максимального потока Второй проход алгоритма После второго прохода: Шаг 4. Выдать j. Конец работы алгоритма.