Условия достижимости, базы дуг и растущие деревья - презентация, доклад, проект скачать

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

Условия достижимости, базы дуг и растущие деревья, слайд №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

Содержание ▲

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

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

Слайд 1

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

Условия достижимости, базы дуг и растущие деревья Лекция № 10

Слайд 2

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

СОДЕРЖАНИЕ Часть 1. Достижимость вершин. Часть 2. Базы дуг. Часть 3. Растущие ориентированные деревья.

Слайд 3

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

Часть 1 Условия достижимости

Слайд 4

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

Достижимость вершин На ориентированном графе G(X,U) t-я вершина считается достижимой из вершины s-ой, если существует хотя бы один путь, ведущий из s-ой вершины в t-ю. Так, 5-я вершина достижима из 1-й.

Слайд 5

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

МАТРИЦА ДОСТИЖИМОСТИ ВЕРШИН Матрица смежности вершин Граф Матрица достижимости вершин

Слайд 6

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

Часть 2 Базы дуг

Слайд 7

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

БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Базой дуг ориентированного графа G(X,U) с матрицей достижимости вершин «М» называется такое подмножество дуг U’ множества U, что: граф G(X,U’) обладает такой же матрицей достижимости вершин M’, что и исходный граф G(X,U). Удаление любой дуги, принадлежащей базе U’, изменяет условия достижимости вершин .

Слайд 8

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

ПРИМЕР 1 Матрица смежности вершин Граф G(X,U) Матрица достижимости вершин Суграф G(X,U’) Суграф G(X,U’’) Суграф G(X,U’’’)

Слайд 9

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

МИНИМАЛЬНАЯ БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Минимальной базой дуг взвешенного ориентированного графа G(X,U) с матрицей достижимости вершин «М» называется такое подмножество дуг U’ множества U, что: граф G(X,U’) обладает такой же матрицей достижимости вершин M’, что и исходный граф G(X,U); суммарный вес дуг подмножества U’ минимален.

Слайд 10

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

ПРИМЕР 2 G(X,U) и М G(X,U’) и M’ G(X,U”) и M” M = M’= M”= Матрица достижимости вершин

Слайд 11

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

СВОЙСТВА БАЗ ДУГ Теорема 1. Каждый ориентированный граф обладает по крайней мере одной базой дуг. Теорема 2 (Кёнига): Ориентированный граф без контуров обладает единственной базой дуг. Теорема 3 (Гольдберга) : Число дуг любой базы дуг U’ ориентированного графа G(X,U), множество контуров которого не пусто, не превышает величины Y = 2(│X│-1), т.е. │U’│≤ 2│X│-2.

Слайд 12

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

АЛГОРИТМ ПОИСКА МИНИМАЛЬНОЙ БАЗЫ ДУГ

Слайд 13

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

ПРИМЕР 3

Слайд 14

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

САМОСТОЯТЕЛЬНО: Определить минимальную базу дуг на графе G(X,U):

Слайд 15

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

Часть 3 Растущие ориентированные деревья

Слайд 16

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

МИНИМАЛЬНЫЕ РАСТУЩИЕ ОРИЕНТИРОВАННЫЕ ДЕРЕВЬЯ Содержательная постановка задачи: требуется на заданном взвешенном ориентированном графе G(X,U) выделить подграф - дерево G’(X’,U’) с корнем в заданной s-ой вершине такой, что: Все вершины, достижимые из s-й вершины на G(X,U), также достижимы из той же вершины на G’(X’,U’). Суммарный вес дуг множества U’ минимален.

Слайд 17

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

ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ

Слайд 18

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

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

Слайд 19

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

СВОЙСТВА МИНИМАЛЬНЫХ РАСТУЩИХ ДЕРЕВЬЕВ Величина является нижней границей суммарного веса дуг минимального дерева. Если граф G(X,U) не содержит контуров, то отвечает оптимальному значению целевой функции. (Сравнить с теоремой Кёнига).

Слайд 20

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

ПРИМЕР 4

Слайд 21

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

АЛГОРИТМ ВЫДЕЛЕНИЯ МИНИМАЛЬНОГО ДЕРЕВА НА ГРАФЕ БЕЗ КОНТУРОВ Шаг 1. На исходном графе G(X,U) удаляются все вершины, в которые отсутствуют пути из s-й вершины, являющейся корнем дерева. Полученный граф вновь обозначаем G(X,U). Шаг 2. Шаг 3. Дуги (p,j), определенные на предыдущем шаге, принадлежат множеству U’. Шаг 4. Конец алгоритма.

Слайд 22

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

САМОСТОЯТЕЛЬНО:

Слайд 23

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

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ На полученном орграфе: 1. Определить минимальный разрез. 2. Удалить дуги минимального разреза на исходном графе G(X,U). 3. На полученном графе G’(X’,U’) построить: А) матрицу смежности вершин; Б) минимальную базу дуг В) минимальное растущее дерево с корнем в вершине – источнике.

Слайд 24

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

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9

Слайд 25

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

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18

Слайд 26

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

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27

Слайд 27

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

Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 1 - 3 Шаг 1. На исходном графе G(X,U) удаляются все вершины, в которые отсутствуют пути из s-й вершины, являющейся корнем дерева. Полученный граф вновь обозначаем G(X,U). Шаг 2. Выбирается дуга с минимальным весом, заходящая в каждую вершину подмножества . Шаг 3. Если на множестве выбранных дуг есть дуга (s,j), исходящая из s-й вершины, то перейти к шагу 4, в противном случае – к шагу 6.

Слайд 28

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

Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 4 - 6 Шаг 4. Вершина j-я «стягивается» в s-ю. Если при этом граф «стянулся» в одну вершину, то перейти к шагу 9, в противном случае – к шагу 5. Шаг 5. Если образуются пары параллельных и согласно ориентированных дуг, то остаётся одна из них, вес которой меньше. Перейти к шагу 2. Шаг 6. Каждой j-й вершине (j ≠ s) присваивается потенциал p(j); где r(i,j)* - дуга, выбранная на шаге 2 последней итерации.

Слайд 29

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

Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 7 - 9 Шаг 7. На множестве вершин выбирается такая, потенциал которой минимален. Шаг 8. Полагая, что выбранная на шаге 7 вершина является j-й, выполняются следующие две операции: дуга (i,j), помеченная звездочкой «*», теряет эту пометку, а дуга (k,j), такая, что: её приобретает. Перейти к шагу 3. Шаг 9. Конец алгоритма. «Стянутые» дуги образуют минимальное дерево.