Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Экономико-математические методы и модели
Содержание
- 1. Экономико-математические методы и модели
- 2. Учебные вопросыОсновы теории графов:Основные понятия и определения.Цикл Эйлера.Гамильтонов цикл.Алгоритм ПримаАлгоритм КраскалаЛекция 9 ЭМММ09.04.2020
- 3. Основы теории графовТеория графов изучает математические объекты, описывающие связи между элементами конечного множества09.04.2020Лекция 9 ЭМММ
- 4. Основные понятия теории графовГрафом называется тройка , где
- 5. Ребро – неориентированная дуга. Граф называется неориентированным, если
- 6. Наглядное представлениеОдному графу можно сопоставить несколько графических
- 7. Табличное (матричное) представление09.04.2020Лекция 9 ЭМММ
- 8. Связность графаМаршрутом называется такая конечная или бесконечная последовательность
- 9. Цикл ЭйлераСреди таких задач наибольшей известностью пользуется задача
- 10. В ходе рассуждений Эйлер пришёл к следующим
- 11. Гамильтонов циклГамильтонов путь — маршрут, содержащий каждую вершину графа
- 12. Взвешенный граф (сеть)Сетью называется граф, элементам которого поставлены
- 13. Построение остовного дереваВ семь населенных пунктов нужно
- 14. Математическая постановкаПредположим, что задан связный граф , и
- 15. Алгоритм Прима —алгоритм построения минимального остовного дерева взвешенного
- 16. Алгоритм ПримаНаходим ребро минимального веса (V1, V6
- 17. Алгоритм КраскалаАлгоритм, более привлекательный в вычислительном отношении,
- 18. Алгоритм КраскалаНаходим ребро минимального веса 1: (V1,
- 19. Скачать презентанцию
Учебные вопросыОсновы теории графов:Основные понятия и определения.Цикл Эйлера.Гамильтонов цикл.Алгоритм ПримаАлгоритм КраскалаЛекция 9 ЭМММ09.04.2020
Слайды и текст этой презентации
Слайд 2Учебные вопросы
Основы теории графов:
Основные понятия и определения.
Цикл Эйлера.
Гамильтонов цикл.
Алгоритм Прима
Алгоритм
Краскала
Слайд 3Основы теории графов
Теория графов изучает математические объекты, описывающие связи между
элементами конечного множества
09.04.2020
Лекция 9 ЭМММ
Слайд 4Основные понятия теории графов
Графом называется тройка , где
M — непустое конечное
множество вершин,
N — конечное множество дуг, соединяющих вершины,
T — отображение
из N в M × M, которое сопоставляет каждой дуге упорядоченную пару вершин. Первая из них называется началом этой дуги, а вторая — концом дуги.M ={A, B, C, D, E}
N = {1, 2, 3, 4, 5},
T(1) = (D,A); T(2) = (D,B);
T(3) = (B,C); T(4) = (C,E); T(5) = (E,D);
09.04.2020
Лекция 9 ЭМММ
Слайд 5Ребро – неориентированная дуга.
Граф называется неориентированным, если каждая его дуга не
ориентирована, ориентированным (орграфом), если ориентированы все его дуги, смешанным, если есть как
ориентированные, так и неориентированные дуги.Петля – это дуга, начальная и конечная вершина которой совпадают.
Вершины, прилегающие к одному и тому же ребру, называются смежными.
Полным называется граф, в котором каждые
две вершины смежные.
Основные понятия теории графов
09.04.2020
Лекция 9 ЭМММ
Слайд 6Наглядное представление
Одному графу можно сопоставить несколько графических представлений.
Изображение призвано
лишь показать, какие пары вершин соединены рёбрами, а какие — нет.
Граф
можно изобразить графически: сопоставить его вершинам точки, а дугам – линии, идущее от начальной вершины к конечной. ВАЖНО: Форма линии и расположение вершин на рисунке произвольны.
09.04.2020
Лекция 9 ЭМММ
Слайд 8Связность графа
Маршрутом называется такая конечная или бесконечная последовательность ребер, что каждые
два соседних ребра имеют общую вершину.
Маршрут называется циклическим, если его конечная
вершина совпадает с начальной.Циклический маршрут называется циклом, если каждое его ребро встречается в нем не более одного раза; вершины могут повторяться и несколько раз.
Две вершины А и В называются связанными, если существует маршрут с концами А и В.
Граф называется связным, если любая пара его вершин связана.
09.04.2020
Лекция 9 ЭМММ
Слайд 9Цикл Эйлера
Среди таких задач наибольшей известностью пользуется задача о семи кёнигсбергских
мостах: в городе Кёнигсберге в начале XVIII века было семь
мостов. Возник вопрос: возможна ли такая прогулка, в которой путь пройдет по всем мостам, и по каждому мосту ровно один раз.Этот вопрос был предложен знаменитому Леонарду Эйлеру, и в 1735 г. он эту задачу решил: нельзя.
Долгое время отдельные задачи теории графов появлялись как занимательные задачи, которые легко формулиро-вались, но были почему-то очень трудны для решения.
09.04.2020
Лекция 9 ЭМММ
Слайд 10В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин
(к которым ведёт нечётное число рёбер) графа должно быть чётно.
Не может существовать граф, который имел бы нечётное число нечётных вершин.Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Карта из статьи 28-летнего Эйлера в трудах Санкт-Петербургской Академии наук
Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.
09.04.2020
Лекция 9 ЭМММ
Слайд 11Гамильтонов цикл
Гамильтонов путь — маршрут, содержащий каждую вершину графа ровно один раз.
Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.
Уильям
Роуэн ГамильтонГамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
09.04.2020
Лекция 9 ЭМММ
Слайд 12Взвешенный граф (сеть)
Сетью называется граф, элементам которого поставлены в соответствие некоторые
параметры (стоимость, расстояние, пропускная способность и т.п.).
Сеть автомобильных дорог
09.04.2020
Лекция 9
ЭМММ
Слайд 13Построение остовного дерева
В семь населенных пунктов нужно провести кабельное телевидение.
Определить маршруты прокладки кабелей вдоль существующих дорог, схема которых представлена
на графе, таким образом, чтобы общая длина была минимальной.09.04.2020
Лекция 9 ЭМММ
Слайд 14Математическая постановка
Предположим, что задан связный граф , и каждой его дуге jN сопоставлено
некоторое число w(j), называемое весом или длиной этой дуги.
Сумму весов дуг дерева называют весом дерева.
Требуется найти такое основное дерево, у которого вес был бы минимален.
Такое дерево называют минимальным остовным деревом.
Рассмотрим два метода: алгоритм Прима и алгоритм Краскала
09.04.2020
Лекция 9 ЭМММ
Слайд 15Алгоритм Прима
—алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.
Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом
Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э.Дейкстрой в 1959 году.Суть алгоритма: находим ребро минимального веса и выделяем подмножество V* связывающих его вершин. Для всех вершин выделенного подмножества находим ребро с минимальным весом среди всех ребер, ведущих к вершинам, не входящим пока в подмножество V*. Включаем соответствующую вершину в подмножество V*. И так далее, пока все вершины графа не будут включены в подмножествоV*
09.04.2020
Лекция 9 ЭМММ
Слайд 16Алгоритм Прима
Находим ребро минимального веса (V1, V6 ) = 1.
Вводим эти вершины в множество V*={ V1,V6}.
Выбираем ребро минимального
веса, исходящее из вершин V*: (V1, V4)=3.Добавляем V4 в V*: V*={V1, V4, V6}
Выбираем ребро минимального веса, смежное с вершинами V*: (V4, V5)=1;
добавляем вершину V5 в V*: V*={V1, V4, V5, V6}
Выбираем ребро минимального веса, смежное с вершинами V*: (V4, V2 ) = 3;
добавляем вершину V2 в V*: V*={V1, V2, V4, V5, V6}.
Выбираем ребро минимального веса, смежное с вершинами V*: (V2 ,V7) = 1; добавляем вершину V7 в V*: V*={V1, V2, V4, V5, V6, V7}.
Выбираем ребро минимального веса, смежное с вершинами V*: (V2, V3 ) = 2; добавляем вершину V3 в V*: V*={V1, V2, V3, V4, V5, V6, V7}.
Неохваченных вершин не осталось.
Длина остовного дерева: L= 1+3+1+3+1+2 = 11
09.04.2020
Лекция 9 ЭМММ
Слайд 17Алгоритм Краскала
Алгоритм, более привлекательный в вычислительном отношении, был предложен Джозефом Краскалом в
1957 г.
Алгоритм состоит из двух фаз.
Джозеф Краскал
На подготовительной фазе
все дуги удаляются из дерева и упорядочиваются по возрастанию их весов. В графе остаются только вершины, каждая из которых образует отдельную компоненту связности.Во второй фазе дуги перебираются в порядке возрастания веса. Если начало и конец очередной дуги принадлежат одной и той же компоненте связности, дуга игнорируется. Если же они лежат в разных компонентах связности. дуга добавляется к графу, а эти две компоненты связности объединяются в одну. Если число компонент связности дойдет до 1, цикл завершается досрочно.
09.04.2020
Лекция 9 ЭМММ
Слайд 18Алгоритм Краскала
Находим ребро минимального веса 1: (V1, V6 ) =
1.
Вводим вершины в множество V*={ V1,V6}
Находим ребро веса
1: (V2, V7) = 1. Вводим вершины в множество V*={ V1,V2,V6,V7}
Находим ребро веса 1: (V4, V5) = 1.
Вводим вершины в множество V*={ V1,V2, V4,V5, V6,V7}
Ребер веса 1 больше нет.
Теперь вводим ребра веса 2, так, чтобы не образовать циклы, но повышать связность графа.
Вводим в дерево ребро веса 2: (V3, V7) = 2.
Вводим вершины в множество V*={ V1,V2, V3, V4,V5, V6,V7}
Ребер веса 2 (не образующих циклов с существующими) больше нет.
Теперь вводим ребра веса 3, так, чтобы не образовать циклы, но повышать связность графа.
Находим ребро веса 3: (V1, V4) = 3.
Находим ребро веса 3: (V4, V7) = 3.
Все вершины включены в дерево. Граф связный.
Вес дерева L = 1+1+1+2+3+3 = 11.
09.04.2020
Лекция 9 ЭМММ
