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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Условия достижимости, базы дуг и растущие деревья, слайд №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
Описание слайда:
Условия достижимости, базы дуг и растущие деревья Лекция № 10

Слайд 2


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

Слайд 3


Часть 1 Условия достижимости
Описание слайда:
Часть 1 Условия достижимости

Слайд 4


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

Слайд 5


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

Слайд 6


Часть 2 Базы дуг
Описание слайда:
Часть 2 Базы дуг

Слайд 7


БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Базой дуг ориентированного графа G(X,U) с матрицей достижимости вершин «М» называется такое подмножество дуг U’ множества U, что: граф G(X,U’) обладает такой же матрицей достижимости вершин M’, что и исходный граф G(X,U). Удаление любой дуги, принадлежащей базе U’, изменяет условия достижимости вершин .
Описание слайда:
БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Базой дуг ориентированного графа 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’’’)
Описание слайда:
ПРИМЕР 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’ минимален.
Описание слайда:
МИНИМАЛЬНАЯ БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Минимальной базой дуг взвешенного ориентированного графа 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”= Матрица достижимости вершин
Описание слайда:
ПРИМЕР 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.
Описание слайда:
СВОЙСТВА БАЗ ДУГ Теорема 1. Каждый ориентированный граф обладает по крайней мере одной базой дуг. Теорема 2 (Кёнига): Ориентированный граф без контуров обладает единственной базой дуг. Теорема 3 (Гольдберга) : Число дуг любой базы дуг U’ ориентированного графа G(X,U), множество контуров которого не пусто, не превышает величины Y = 2(│X│-1), т.е. │U’│≤ 2│X│-2.

Слайд 12


АЛГОРИТМ ПОИСКА МИНИМАЛЬНОЙ БАЗЫ ДУГ
Описание слайда:
АЛГОРИТМ ПОИСКА МИНИМАЛЬНОЙ БАЗЫ ДУГ

Слайд 13


ПРИМЕР 3
Описание слайда:
ПРИМЕР 3

Слайд 14


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

Слайд 15


Часть 3 Растущие ориентированные деревья
Описание слайда:
Часть 3 Растущие ориентированные деревья

Слайд 16


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

Слайд 17


ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ
Описание слайда:
ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ

Слайд 18


ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
Описание слайда:
ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

Слайд 19


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

Слайд 20


ПРИМЕР 4
Описание слайда:
ПРИМЕР 4

Слайд 21


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

Слайд 24


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9

Слайд 25


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18

Слайд 26


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27

Слайд 27


Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 1 - 3 Шаг 1. На исходном графе G(X,U) удаляются все вершины, в которые отсутствуют пути из s-й вершины, являющейся корнем дерева. Полученный граф вновь обозначаем G(X,U). Шаг 2. Выбирается дуга с минимальным весом, заходящая в каждую вершину подмножества . Шаг 3. Если на множестве выбранных дуг есть дуга (s,j), исходящая из s-й вершины, то перейти к шагу 4, в противном случае – к шагу 6.
Описание слайда:
Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 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 последней итерации.
Описание слайда:
Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 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. Конец алгоритма. «Стянутые» дуги образуют минимальное дерево.
Описание слайда:
Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 7 - 9 Шаг 7. На множестве вершин выбирается такая, потенциал которой минимален. Шаг 8. Полагая, что выбранная на шаге 7 вершина является j-й, выполняются следующие две операции: дуга (i,j), помеченная звездочкой «*», теряет эту пометку, а дуга (k,j), такая, что: её приобретает. Перейти к шагу 3. Шаг 9. Конец алгоритма. «Стянутые» дуги образуют минимальное дерево.

Слайд 30


ПРИМЕР 5
Описание слайда:
ПРИМЕР 5

Слайд 31


САМОСТОЯТЕЛЬНО: Построить минимальное дерево с корнем в 1-й, 2-й, …, 7-й вершине на графе G(X,U):
Описание слайда:
САМОСТОЯТЕЛЬНО: Построить минимальное дерево с корнем в 1-й, 2-й, …, 7-й вершине на графе G(X,U):

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию