Алгоритмы теории графов. Лекция №8 презентация

Содержание

Слайд 2

Алгоритм построения кратчайшего пути Алгоритм Дейкстры «Алгоритмы теории графов» Лекция

Алгоритм построения кратчайшего пути
Алгоритм Дейкстры

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и

технология производства ЭА» http://nanotech.iu4.bmstu.ru
Слайд 3

Алгоритм построения кратчайшего пути Алгоритм Дейкстра «Алгоритмы теории графов» Лекция

Алгоритм построения кратчайшего пути
Алгоритм Дейкстра

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и

технология производства ЭА» http://nanotech.iu4.bmstu.ru
Слайд 4

Алгоритм построения кратчайшего пути Алгоритм Беллмана-Форда «Алгоритмы теории графов» Лекция

Алгоритм построения кратчайшего пути
Алгоритм Беллмана-Форда

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и

технология производства ЭА» http://nanotech.iu4.bmstu.ru
Слайд 5

Алгоритм построения кратчайшего пути Алгоритм Беллмана-Форда «Алгоритмы теории графов» Лекция

Алгоритм построения кратчайшего пути
Алгоритм Беллмана-Форда

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и

технология производства ЭА» http://nanotech.iu4.bmstu.ru
Слайд 6

Хроматическое число графа «Алгоритмы теории графов» Лекция №8 Кафедра ИУ4

Хроматическое число графа

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и технология производства

ЭА» http://nanotech.iu4.bmstu.ru

классов

Слайд 7

Двухдольный граф «Алгоритмы теории графов» Лекция №8 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Двухдольный граф

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и технология производства ЭА»

http://nanotech.iu4.bmstu.ru
Слайд 8

Алгоритм раскраски Алгоритм неявного перебора при раскраске графа Предположим, что

Алгоритм раскраски
Алгоритм неявного перебора при раскраске графа
Предположим, что множество вершин как-то

упорядочено и xi — i-я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:
1. Окрасить xi в цвет 1.
2. Каждую из оставшихся вершин окрашивать последовательно: вершина xi окрашивается в цвет с наименьшим возможным «номером» (т. е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной xi).

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Слайд 9

Алгоритм раскраски Алгоритм неявного перебора при раскраске графа «Алгоритмы теории

Алгоритм раскраски
Алгоритм неявного перебора при раскраске графа

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4

«Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru
Слайд 10

Алгоритм раскраски Алгоритм неявного перебора при раскраске графа «Алгоритмы теории

Алгоритм раскраски
Алгоритм неявного перебора при раскраске графа

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4

«Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

1

2

3

1

4

2

4

Слайд 11

Алгоритм раскраски Последовательный алгоритм раскраски графа Шаг 1. Составить упорядоченный

Алгоритм раскраски
Последовательный алгоритм раскраски графа
Шаг 1. Составить упорядоченный в порядке убывания

степеней вершин список.
Шаг 2. Первая вершина окрашивается в цвет 1 и удаляется из списка.
Шаг 3.Просматривая список, в текущий цвет раскрашиваются и удаляются из списка все вершины, не смежные с выбранной и между собой. Номер цвета увеличивается на 1.
Шаг 4. Далее выбирается первая вершина из списка, она окрашивается в текущий цвет и удаляется.
Шаг 5. Процесс продолжается, пока не будут окрашены все вершины.

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Слайд 12

Алгоритм раскраски Последовательный алгоритм раскраски графа. Пример. «Алгоритмы теории графов»

Алгоритм раскраски
Последовательный алгоритм раскраски графа. Пример.

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование

и технология производства ЭА» http://nanotech.iu4.bmstu.ru
Слайд 13

Алгоритм раскраски Применение - Задачи расписания Распределение ресурсов Распределение регистров

Алгоритм раскраски
Применение
- Задачи расписания
Распределение ресурсов
Распределение регистров в микропроцессорах
Распределение частот для мобильной

связи
Задачи ЭМС
и др.

«Алгоритмы теории графов»
Лекция №8

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Имя файла: Алгоритмы-теории-графов.-Лекция-№8.pptx
Количество просмотров: 52
Количество скачиваний: 0