Презентация на тему: БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных

БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных
1/23
Средняя оценка: 4.1/5 (всего оценок: 49)
Код скопирован в буфер обмена
Скачать (3024 Кб)
1

Первый слайд презентации

БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных графов и вопросы их реализации САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ ТИМАНОВСКАЯ Т. С., группа 4518

Изображение слайда
2

Слайд 2

Contents Введение 3 01 Необходимые понятия 5 02 Раскраска графов 7 03 Алгоритмы раскраски 10 04 Применение раскраски графов 14 05 Содержание 06 Заключение 22

Изображение слайда
3

Слайд 3

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

Изображение слайда
4

Слайд 4

Введение Объект исследования дипломной работы – алгоритмы раскраски планарных графов и их практическое применение. Предмет исследования – характеристики эффективности алгоритмов, области применения алгоритмов раскраски графов. Цель работы – программная реализация и сравнительный анализ алгоритмов раскраски графов, определение области их практического применения. Задачи работы : Рассмотреть основные понятия теории графов Рассмотреть основные понятия и теоремы раскраски графов Рассмотреть алгоритмы раскраски графов Реализовать алгоритмы программно Провести сравнительный анализ реализованных алгоритмов Описать практические способы применения раскраски графов

Изображение слайда
5

Слайд 5

Необходимые понятия Граф G =(S,U) – это конечное множество вершин S и множество ребер U Если ребра имеют направление связи, то они называются дугами, а граф ориентированным ( орграфом ) Смежные вершины - это вершины графа между, соединенные ребром Если в графе существует путь между любыми двумя парами его вершин, то такой граф – связный, иначе - несвязный ( изображен справа )

Изображение слайда
6

Слайд 6

Необходимые понятия Если любые две вершины графа смежные, то такой граф называется полным K n Если любые два ребра графа не имеют точек пересечения, помимо инцидентной вершины, то такой граф - плоский, а любой, изоморфный ему - планарный Количество ребер инцидентных вершине графа - степень вершины Основные способы задания графа – матрицы смежности и инциденций Внутренне устойчивое множество вершин состоит из попарно несмежных вершин графа

Изображение слайда
7

Слайд 7

Раскраска графа Раскраской вершин графа G в k цветов называется функция ρ:V(G)→M, где | M|=k. Раскраска ρ называется правильной, если ρ(v)≠ρ(u) для любой пары смежных вершин u и v χ(G) - хроматическое число графа G – наименьшее натуральное число, для которого существует правильная раскраска вершин графа G в такое количество цветов На данный момент не существует точной формулы для расчета хроматического числа графа, но существуют оценки для него, позволяющие определить интервал значений k- раскрашиваемый граф - граф, который можно правильно раскрасить в k цветов Теорема о пяти красках : любой планарный граф можно правильно раскрасить в 5 цветов. Появилась на основе гипотезы о четырех красках, которая была доказана только для случаев, когда вершин в графе не более 38, - это самая известная проблема раскраски графов, имеющая долгую историю попыток доказать ее истинность

Изображение слайда
8

Слайд 8

Раскраска графа Оценки хроматического числа графа : χ(G)≥⌈ 11/6 ⌉ ⟹ χ(G)≥ 1 χ(G)≤ 11 - 6 +1 ⟹ χ(G)≤ 6 3 ≤χ(G)≤ 4 χ(G)≤ 5.81 Расчеты проведены в соответствии с формулами, изложенными на стр. 14 ВКР, с начальными значениями для изображенного графа : n=11, m=14, alpha(G)=6 ( мощность максимального независимого подмножества вершин { v 0,v 2,v 3,v 5,v 6,v 10 })

Изображение слайда
9

Слайд 9

Раскраска графа Раскраской ребер графа G в k цветов называется функция ρ:E(G)→ M, где | M|=k. Раскраска ρ называется правильной, если ρ(e)≠ρ(e ') для любой пары смежных ребер e и e ’ χ' (G) – реберное хроматическое число или хроматический индекс графа G – наименьшее натуральное число, для которого существует правильная раскраска ребер графа G в такое количество цветов Теорема Визинга для графов, допускающих кратные ребра : п усть граф G – граф без петель. Тогда χ'(G)≤ Δ(G)+μ( G). Где Δ(G) - максимальная из степеней вершин графа, μ( G) - максимальная кратность ребер в графе Раскраска ребер связана с вершинной раскраской графа, и смогла дополнить гипотезу о четырех красках, доказав теорему : для того чтобы хроматическое число графа было равно 4, необходимо и достаточно, чтобы его ребра до п ускали такую раскраску в три цвета, при которой никакие два ребра одной грани не были раскрашены одинаково

Изображение слайда
10

Слайд 10

Алгоритмы раскраски графов В моей работе приведено 6 общих алгоритмов раскраски ( и определения хроматического числа ) графов и один частный алгоритм ( Виндерсона ), который позволяет оптимально раскрасить граф, зная его хроматическое число Все алгоритмы кроме последнего, можно разделить на группы : точные алгоритмы ( Вейсманна, Лорьера - Новикова ) эвристические алгоритмы поиска правильной раскраски ( жадный, перебор, рекурсивный ) Так же заметно, что все эвристические алгоритмы, кроме жадного, основаны либо на поиске независимых подмножеств вершин графа, либо на предварительном перед жадным способом раскраски упорядочивании вершин

Изображение слайда
11

Слайд 11

Алгоритмы раскраски графов На левом рисунке изображена логика алгоритмов, основанных на выделении независимых множеств вершин графа. На среднем рисунке - принцип жадного алгоритма раскраски и его главный минус : зависимость от способа нумерации вершин. На правом изображена логика работы алгоритма, с использованием упорядочивания вершин по их степеням

Изображение слайда
12

Слайд 12

Алгоритмы раскраски графов Для реализации были выбраны алгоритмы RLF, BSC, жадный алгоритм. Выбор был основан на том, что они представляют собой основные направления алгоритмов раскраски, кроме того, их реализация не требует минимизации булевых функций, в отличие от точных алгоритмов \ alg RLF BSC Greedy |E| |V|\par χ(G) t, mc χ(G) t, mc χ(G) t, mc 15 3 4 3 3 3 1 21 26 3 10 3 8 3 1 41 35 4 29 4 16 4 2 61 42 3 36 4 16 4 2 67 50 4 57 4 21 4 2 101 min( χ(G) ) max( χ(G) ) 1 3 1 4 2 4 2 4 3 7 Алгоритмы были применены к графам из 15, 26, 35, 42, 50 вершин. Все данные графы являются планарными, без петель и кратных рёбер. Изображения графов представлены на стр. 37-38 ВКР. По формулам оценок хро м атического числа в зависимости от количества вершин (|V|) и ребер (| E|) приведены нижние и верхние допустимые значения хроматического числа для каждого из графов.

Изображение слайда
13

Слайд 13

Алгоритмы раскраски графов красный RLF зеленый BSC синий GREEDY |V| t, mc График зависимости времени работы алгоритма от количества вершин По быстродействию наилучший результат показал жадный алгоритм, однако точность его оценки хроматического числа графа не слишком удовлетворительна. Гораздо лучше себя показал в плане точности RLF алгоритм, уступая другим по быстродействию, с его помощью в случае с графом из 42 вершин хроматическое число, найденное алгоритмом, оказалось наименьшим. BSC алгоритм оказался медленнее жадного, и не такой точный как RLF. Возможно, такие показатели алгоритмы дали на конкретно моих входных данных - графы не сильно связные, поэтому сортировка вершин по степеням в алгоритме BSC не повышает его эффективность, а только лишь требует дополнительных временных затрат.

Изображение слайда
14

Слайд 14

Применение раскраски графов Применение раскраски графов для решения задач составления расписаний Составляется граф, вершинами которого являются какие либо мероприятия. Вершины соединим ребром, в случае, если соответствующие мероприятия нельзя проводить одновременно ( не могут использовать дни и те же ресурсы одновременно ), тогда составление расписание сводится к нахождению правильной раскраски полученного графа минимальным количеством цветом при условии, что количество вершин, окрашенных в один цвет, не будет превосходить порогово го значения по логике задачи, если таковое имеется. Сформированный граф и его раскраска будут выглядеть как показано ниже ( при условии количества мероприятий 4, ресурсного ограничения 3, максимальное количество вершин одного цвета 3). Таким же образом раскраску графов применяют при кластерном анализе.

Изображение слайда
15

Слайд 15

Применение раскраски графов Применение раскраски графов для решения задач распределения частот Если представить карту вышек сотовой связи в виде графа, то вершинами его будут зоны покрытия вышек, а смежными они будут, только если имеют общую границу и перекрываются. Станции, в таком случае, не могу работать на одной частоте, из - за помех. Один цвет ( color class) представляет один диапазон частот. Тогда, любая правильная раскраска графа обеспечит функционирование сети без помех, и хроматическое число определяет наименьшее количество диапазонов частот для бесперебойной работы сети. Используется алгоритм основанный на выделении независимых подмножеств вершин.

Изображение слайда
16

Слайд 16

Применение раскраски графов Применение раскраски графов для решения задач распределения регистров Вычисления в машинных регистрах называются интерферентными, если они происходят одновременно на каком-либо участке выполнения программы. Таким образом, необходимо построить граф интерференций : вершины обозначают регистры и все ресурсы используемые программой, ребро между вершинами отображает интерференцию. Тогда задача состоит в раскраске графа в количество цветов равное количеству регистров, то есть хроматическое число графа должно быть равно количеству регистров, чтобы они были распределены верно. Схема процесса раскраски графа показана и результат раскраски ниже.

Изображение слайда
17

Слайд 17

Применение раскраски графов Технология электронных водяных знаков Электронные водяные знаки наносятся на программное обеспечение с целью защиты интеллектуальной собственности. Суть их состоит не в добавлении какого либо кода в программу, а в переводе подписи автора в множество дополнительных ограничений, которые добавляются в оригинал ПО. Так как такая подпись основана на добавлении ограничений, то возможно некоторое ухудшение качества самого ПО. Поэтому необходимо держать баланс между степенью надежности защиты и степенью снижения качества ПО. Раскраска графов применяется в так называемой constraint-based ( основанной на ограничениях ) технологии нанесения электронного водяного знака. Исследования показали, что даже огромный объем информации водяного знака может быть внедрен в граф, и при этом хроматическое число графа, с водяным знаком будет отличаться не более, чем на 1. И даже практически все графы с большим дополнительным объемом информации о водяном знаке могут быть раскрашены в известное число цветов оригинального графа, без увеличения временных затрат. Далее будут изложены три различных подхода к кодированию электронной подписи с помощью алгоритмов раскраски графа.

Изображение слайда
18

Слайд 18

Применение раскраски графов Технология нанесения водяного знака путем добавления ребер Допустим, есть k- раскрашиваемый граф. Мы добавляем ограничения, таким образом увеличивая количество возможных вариантов решения. На схеме штриховкой обозначена область подходящих решений для графа G' ( здесь и далее - граф со встроенным водяным знаком ). Поскольку он включает все ограничения оригинального графа, то решения подходящие для G ' та же подходят для, но обратное неверно. Таким образом есть обозначить n k и n' k количество допустимых раскрасок в k цветов для оригинального и дополненного графа, то шанс отыскать верное решение ( из области S ) возрастает от 1/ n k до 1/ n' k, и, если n k велико, а n' k < < n k, то это обеспечивает хорошую защиту.

Изображение слайда
19

Слайд 19

Применение раскраски графов Технология нанесения водяного знака путем добавления ребер Процесс нанесения водяного знака : Дан граф G=(V,E) и сообщение М, которое надо встроить в ПО, переведенное в бинарный вид M=m_0,m_1... Для каждого бита в М : ищем 2 ближайшие несмежные с текущей вершиной под номером i вершины с номерами i1, i2. Если бит равен 0, то добавляем ребро между i и i1, иначе между i и i2. Требования : i2>i1> i (mod n), и нет такой вершины с номером j несмежной с i, что i2>j>i1. Например, сообщение 1998 10 =11111001110 2, встроенное в граф, будет делать его таким, как показано на рисунке. В измененном графе соединенные нами вершины будут перекрашены в отличные цвета, что сразу обнаружится при сравнении с оригинальным графом.

Изображение слайда
20

Слайд 20

Применение раскраски графов Технология нанесения водяного знака путем поиска независимых подмножеств вершин графа Процесс нанесения водяного знака : Дан граф G=(V,E) и сообщение М, которое надо встроить в ПО, переведенное в бинарный вид M=m_0,m_1... Задача заключается в том, чтобы закодировать с помощью одного или нескольких независимых подмножеств это двоичное сообщение. В начале выбираем вершину номер i, такую, что i в двоичной СС соответствует первым floor(log n) битам в М. Потом, вычеркиваем эту вершину и все смежные с ней, перенумеровываем оставшиеся и повторяем процедуру до тех пор, пока не получится независимое множество, которое окрашивается в один цвет. Далее, вычеркиваем его из оригинального графа, и таким же методом ищем последующие множества, пока полностью не закодируем М. Поскольку вершина может входить в различные независимые множества, а кроме того, важен порядок вершин в независимом множестве в процессе кодировки, то подобрать правильное решение к оригинальному графу по дополненному не представляется возможным за конечное время. Так например сообщение 1998 10 =11111001110 2 скрыто в изображенном графе как 11111 в независимом множестве {v7,v4,v1,v10} и 001110 в { v0,v6,v5,v2} именно в таком порядке.

Изображение слайда
21

Слайд 21

Применение раскраски графов Технология нанесения водяного знака путем добавления вершин и ребер Процесс нанесения водяного знака : Дан граф G=(V,E) и сообщение М, которое надо встроить в ПО, переведенное в бинарный вид M=m_0,m_1... Затем, мы объявляем новую вершину v, и соединяем ее с вершиной соответствующей первым floor(log n) битам в М. Далее, соединяем с вершинами соответствующими floor(log n – i *1 ) битам М. Если одной вершины оказалось мало, то добавляем еще одну и действуем по такому же принципу, пока М не будет полностью закодировано. Выявить наличие такого водяного знака крайне трудно, так как невозможно определить какие из вершин были добавлены. Рассмотренный в работе QP алгоритм нанесения водяного знака и его модификации базируются на первой изложенной технологии, собственно, сам базовый QP алгоритм описывает по шагам основные идеи первого метода – добавления ребер.

Изображение слайда
22

Слайд 22

Заключение В ходе данной работы были : освещены необходимые аспекты теории графов описаны алгебраические основы раскраски графов рассмотрены алгоритмы раскраски графов и три из них реализованы в среде Microsoft Visual Studio 2017 был проведен анализ полученных результатов работы реализованных алгоритмов широко освещена тема прикладного использования раскраски графов подробно разобрана технология нанесения цифровых водяных знаков

Изображение слайда
23

Последний слайд презентации: БАКАЛАВРСКАЯ РАБОТА Практическое применение алгоритмов раскраски планарных

Contents Спасибо за внимание ! И за 4 года в Университете

Изображение слайда